When Google released the YouTube app for the Storm only I was a bit peeved. Looks like Xenozu has tried to rectify the situation by releasing their own free YouTube app that works on more devices. So far this looks like another app that is only available in the App World at this link.
This is not a Google sanctioned app so I cannot promise it will give you the same experience but reports are positive so far. Sadly it looks like you still get the crappy quality 3gp videos that Google provides instead of the h264 videos you see on the iPhone.