Whats the most cross-browser method of embedding videos?

A client of mine wants to put some videos on their website. In the past I've always just converted the video to an FLV, and used something like LongTail Player to play it.

However, nowadays of course lots of people use smartphones such as the iPhone that don't play flash files - so whats the best option? Is it a case of choosing one format, or is it best to go with flash, and then provide a download for iPhone users? I have noticed on some websites I have been viewing on my iphone, you can click on the video and it launches in YouTubes video player - is this perhaps an option?

Views would be appreciated.