If you use the Youtube app on 3G the videos look considerably worse.
A solution for you would be to use the safari browser and visit the youtube site to look for videos. The website was recently optimized for use in the iphone browser. That method will ensure the videos are higher quality. You can make a bookmark icon to the youtube page as well and just treat it like another app on your homescreen.