It is unlikely you'll see native flash support on the iPhone (or very many other mobile platforms) any time soon. The reason is because flash is a very client-intensive endeavor, requiring a decent amount of processing capability to function properly, particularly fp9. Youtube makes it work (afaik) by delivering the content to the iPhone in H264, which is decoded by Apple's hardware H264 decoder (coming soon to an ipod near you). H264's Baseline profile (1.3) is relatively light on the client side, decent for mobile platforms. Ideally, Pandora should (and probably will) shoot for this type of setup, as H264 seems the likely choice for mobile media in the next 12 months, especially on Apple devices, since they're planning on sticking their hardware decoder in all their next-gen products.
Flytunes is pretty awesome (seriously, and you can't beat free!), if they happen to have the station you want... or the podcast you want (they are getting a lot more, which is good!), however, the OP asked about Pandora, which flytunes doesn't do... (flytunes also doesn't stream from last.fm, seeqpod, lala, mp3tunes, or your own iTunes library, or album art, or let you rate your tracks, etc.) So, imh(and biased)o, you get what you pay for (well, maybe a little more in both cases)..