Surely more CPU power often equates to shorter battery life. Which really is very important to most people, considering just how badly batteries still suck.
So personally if it's a difference of battery life, I'd choose the one that uses less power and gives me more time.
If you are watching video constantly, then this is a concern. If your phone is mostly sitting in your pocket waiting for the GSM signal to wake it up, then it's irrelevant.
(And, I have a portable device that plays arbitrary video formats just fine on a rather-big 5" screen for a whole transatlantic flight; 7-8 hours. So the current technology is more than adequate, H.264 or not.)
People complain about the extra CPU power it takes to decode Theora, but if I have to choose between paying extra for a more-powerful CPU or a patent license, I would choose the former. At least I can make use of the more-powerful CPU when I'm not watching videos of cats flushing the toilet.