(and as for text-only browsers... <table> has been around for a LONG time. Surely text-only browsers have some sort of system for coping with them?)
Yes they do, and some of them are quite good at it. Lynx is worst (it does the right-alignment Karl describes), w3m is acceptable and links even puts nice little borders around the cells. Links can even handle frames, it is really quite impressive. There is also a graphical version of Links: http://atrey.karlin.mff.cuni.cz/~clock/twibright/links/
The CPU usage is negligible in text browsers and most graphical browsers, the only common browser that sometimes has problems with complex tables is Netscape 4. Some people have a strange affection towards it, but it really must die as soon as possible. Phoenix, Galeon etc. use the Mozilla engine without the bloat and provide much faster rendering than Netscape 4.
Regards,
Erik