My current understanding of how linuxbios works is very limited but, is there an absolute requirement that this should occur over a serial port?
No, however getting higher speed devices to work may require some amount of working memory, interrupts, etc (the parallel port might be ok however). IMO, once memory is working (and interrupts enabled), much of the hard work is done.