I like Evil Genius, but it takes some work to get to grips with it and it can be very frustrating until you figure out a few tips. I'd strongly recommending glancing through an FAQ first since the manual and in-game hints don't quite give you enough information.
The graphics and atmosphere are fantastically done and really fit the theme well. While the graphics aren't cutting edge, the cartoon style doesn't require super high quality anyway. From that point-of-view, even if this game was remade today, I doubt it would look much better.
The biggest gameplay problem is the way base-building and world domination work together. You need to work the world domination map in order to get money and you need to keep an eye on the map or the minions you sent out will get killed. At the same time, however, you have to keep an eye on your base or you'll be overrun with agents. The problem is you really need to be able to watch both screens at once. If they made it easier to know what was happening on one screen while looking at the other, or if they had better controls on world domination screen (for example, set it to automatically replace lost minions, or automatically hide when agents appear in the same region, or set it to keep heat below a certain threshold) or better AI on the base-building screen (or at least be able to set zones that will automatically tag agents when the enter them), the gameplay would be much smoother.