"What fonts to folks use for their standard "serif" and "san-serif"
font on Linux?"

Well this is indeed a question which depends often on the distribution
itself ;) but for the more recent distributions you may be on the safe
side using the bitstream-fonts.

Check:
http://foundation.gnome.org/press/pr-bitstreamfonts.html

So maybe the Vera-font may be one possible substitution...

On the other hand you may handle this flexible -> e.g. my standard
fonts are some special ones by adobe (times, helvetica, courier) which
are licensed as part of my distribution (and I also have licenses for
mac and win here, so one font-family for all systems)

I don't know - but have you checked the different licenses of fonts?
maybe you'll have a chance to bundle one set with your software, so
you may distribute these with the diffrent versions of pagestream
(win, linux,...)

e.g. actually it seems the windows-fonts are downloadable for free,
and free for usage on your PC (even if it doesn't use Win), so maybe
choose Arial, Times as standard and give some advices for linux users
to install these fonts also.

Maybe go the debian way here:
http://packages.debian.org/unstable/graphics/msttcorefonts.html

They do have an installer for automatic download and install of those
fonts (as it doesn't seems to be legally correct to inculde those
fonts itself..?)

Just my two ?-cents ;)