I think every ad-user has this issue at some point or another, and I really think it depends on the types of ads you're using. If you're using huge, flashing banners across the top of your site and then more large ones down the sides, it's kinda hard to make them look "less ugly." Using smaller ones and placing them in key locations may stand out a bit less, though.
Also, depending on your site, niche, page rank, reputation, etc, you may be able to sell ads to specific companies instead of going through ad programs. You have a lot more control over what goes on your site this way and if you support a company, you might not find the ads so ugly.
