The part about almost any device meant to run Linux having a serial port isn't guaranteed. The reason why most of them have one is that it's just convienent during development. There is nothing stopping you from not having serial at all in a device and some things don't. Some devices only have a JTAG port for reprogramming the firmware EEPROM and nothing else.

The MediaMVP PCB has space for a RS232 level converter which when soldered in will give you that serial port. It also has space for a CF slot but I don't believe anybody has managed to make that work yet. There are pictures of the PCB on the shspvr.com forums.