You just picked two of the more difficult apps to emulate or ahead-of-time translate as your examples of "normal" apps that should be "not so hard!"
Archivers generally have highly optimized compression/decompression routines, which generally means more esoteric instructions and in some edge cases means abusing properties of the microarchitecture to make things faster.
Media players have the same optimized-code issue that archivers do (via codecs), but on top of that demand very accurate audio/video synchronization and support a wide variety of output formats and hardware, which means that media players often add difficult-to-translate display and audio output pipeline hacks on top of difficult-to-translate optimization.
Starcraft I ran on x86 CPUs without MMX or SSE, and I wouldn't be surprised if it didn't use x87 floating point either although I'm venturing into speculation territory there. Plus, Starcaft I used DirectDraw and what amounts to a framebuffer - the easiest possible output device to emulate.