The new Amazon Market for Android will have a for-fee version of Angry Birds - for sure that won't have ads.
I've noticed ads are now occasionally much larger in TweetCaster, and have noticed that in Angry Birds every once in a while I'm thrown from the game to the browser, where a full-page for Angry Birds is displayed. I'm ok if they're in the app itself and don't take up too much space, but to be thrown out to the browser really REALLy annoyed me...