An advertisement in conjunction with running an application the 1st time would probably be acceptable to everyone. All the better if the ad is relative to the application. For example, Maemo Mapper having an add like that for a Bluetooth GPS receiver. I'd also make the ad viewable in the About popup. Another example is an IM application which beyond configuration of a Social Network may also be an add. Seeing the same ad every time we run an application would be too annoying like a web site that never changes. IMHO our screens are too small to give up pixels to an ad. A better model might be like Google Adwords that are retrieved because they relate to the content the user received or entered. They may not be reasonable to implement but it's worth considering.