Some modern PDAs have good enough battery life to do most flights - 4 hours plus. Look for one that is physically larger as it will likely have a bigger battery. Examples include the iPAQ 4300 series with the built in keyboard, or slightly less so the iPAQ 4700 series.
I wouldn't shy away from Bluetooth. I've used it with half a dozen different PDAs, a similar number of mobile phones, laptops and a couple of GPS receivers, all without problems. Thousands of people use AnywhereMap with it regularly. Of course, a cable is going to be more reliable I suppose, provided it has a good connection (the sockets on the bottom of many PDAs are pretty flimsy) and provided that using it doesn't stop you using external power if you want to.
I also wouldn't let the suggested need for an external (to the plane) antenna put you off either. Of course it will be better and is desirable, but an external one at the bottom of the windscreen is pretty good. That you can drive through central London with the GPS receiver on the passenger seat of the car without it losing a signal shows just how good modern units are.
Screen size - the new VGA models (such as the iPAQ 4700) are a big improvement in this area, though older models are perfectly workable. Make sure that whatever software you're using supports VGA, unless you're just interested in everything appearing bigger on the screen (as opposed to seeing more information) which is what will happen if it doesn't.