So I'm trying to get back into the habit of going to the gym, and I figured it would help me get my butt in gear if I had some way to watch movies/(legally DVRed) TV shows while I'm exercising.

What I'm looking for (in rough order of importance):

-decent screen size: it'll be likely a couple feet in front of me, so a 2" screen is not going to cut it. Widescreen would be a pretty big plus.

-support for a good variety of file formats: I'm not going to lie, if it could play .mkv with h.264 encoding I would be very very happy (ALL MY MEDIA FILES ARE LEGALLY OBTAINED). I don't think anything like that exists though, so I'd settle for something for which software exists that can quickly and painlessly convert video from my computer onto something playable on the device.

-plenty of storage space: meh, this one isn't as important; I can't see where I'd need more than a couple hours of video storage, but it's always nice to have lots of room. I'm probably leaning towards something with flash memory.

-good battery life: again, a few hours is all I really need. Bonus points if a replacement battery doesn't cost more than an entire new device though.

And that's basically it.

Look at what Cowon and Archos have, especially Cowon.

I just bought a portable dvd player for $90. Plays rewriteable dvds, so thatd solve the storage issue pretty well. 9" widescreen too. Probably not what your looking for though

I'm rather drooling over the Archos 7; it looks pretty nice.

Edit: And now I'm reading some customer reviews on Amazon that are a bit scary.

if you can find an iRiver PMP-120 or 140 on ebay, pick it up. it plays a lot of different file formats, has a 3.5" screen, is fairly lightweight, and batteries are only like 10$ a pop.

battery life is good for a couple hours of video.

only problem with it is it uses more battery just sittin there on than it does playing anything.

Make a laptop mounting tray.

You'll be ultimate fitness uber-geek then.

rio karma ftw

psp and spare memory sticks

Look at Cowon. http://www.cowonamerica.com/ They are pretty much any thing you could ask for in a PMP. No BS DRMed suits, plays almost everything, SDHC flash expandable, some even have freaking composite video out, and will do 30fps 720p if you use it!

EDIT: The O2 does do HD.264 .mkv!