Are you resizing the video at all in the browser? When messing around with it, I found that I could play 720p video with the video tag smoothly without any formatting in Chrome and Firefox, but that setting it's size attributes to something other than the actual file size made it slow to the point of being unwatchable.
As a result, I'm now working on using Flash to play the video in all cases except when Flash does not exist, because this is just not working out for me. Maybe I'm just not doing it right, but it beats me what the issue is.