Doing targeted advertising that
is utility is the best way to make ads not suck.
The main reason advertising is annoying is because we are looking for something else, we don't need it right now, or its the wrong audience.
If you had a huge spare tire and wanted rock hard abs, and the advertisement could prove the safety of your purchase, you would say "HELL YEAH!"
When I was 16 the advertisement for Proactiv was very engaging. It worked and I was amazed. I'm no longer a zitty teenager so now I find their advertisements annoying.
I recently joined the Spiceworks team, and it is free software. It is advertisement driven, but most in the case where you need it. It is IT management software. As an example, if you see your SQL server getting slammed, you could see an ad that offers you RAM for that specific machine. Does this advertisement suck? Probably not.
One reason advertising could suck is due to audience. If you go to Digg (which has a wide audience) you are going to get wide or undirected ads. This is why targeted advertisement is all the rage these days - because its less annoying, and more to the point effective and win-win in more cases than not.
I'd say to make advertising not suck, don't involve yourself in communities without a common interest or goal. If you are an IT manager and you are in an IT community, you will more than likely get IT advertisements. If you are watching MTV... well...