don't hold me to this, but i think you can get MK3/umk3 (not sure which) as a pack-in on the special edition of one of the xbox-era MK games.
also, i think you can get them in the Midway arcade legends games, but they might be named something else, never picked any of them up, but they're just compilations of Midway arcade games, and i know you could at least get MK1 this way
as far as the HDD space needed, it all depends on which system you want
NES, in total is less than 200 megs, i think
snes, is a little under a gig
genesis is about the same
n64 is 2-3 gigs iirc, though a lot of games don't run very well( ex. Goldeneye, it actually runs well, but is IMPOSSIBLE to play with the xbox controller)
arcade/neo geo games really vary, never put the full set on my xbox
anything cd based will be huge
course, that's for the full romsets.
if you're talking individual games, that's a whole different story