It depends on the what format your videos are (FLV, MP4, WMV, Quicktime, etc.)
I'm near finishing up on a site with several videos and had favorable success during testing with Longtail's JW Player, Viper's Video Tags, FV WordPress Flowplayer, and Flowplayer for WordPress. We wanted a little more control over some aspects of the players appearance, and opted for an offsite solution. We found two, Flowplayer and Adobe Flash Media Playback. While the Flowplayer player is very customizable, we found that the Adobe Media Player offered enough options and was dead simple to install.
In both cases, the player is hosted by their CDN, and with the Adobe all that's necessary is to copy the generated code and paste it into a page. Flowplayer is also very good, but required a little more effort to set the player up. Adobe and it's simplicity is perfect for my client who is not terribly versed in web page building or Wordpress.
We looked at HTML5, but decided not to go that route since it's still in development, and his site will have a client base that's pretty diverse. Perhaps down the road a bit, who knows...
If you want to have a look at the Adobe player output, send me an e-mail to davegehr@NOSPAMgmail.com (remove the NOSPAM). Make sure you include your handle, helgatheviking, somewhere in your message so I know it's you. The site is still located on my own server space while I tidy things up before loading to the client's site.
[EDIT] Forgot to mention that we are using Flash wrapped MP4's with a Quicktime fallback for iPhone and some Apple users.
