Some general principles:
(I'm not going to put "musts" and "nevers" because there aren't any; these are my preferences. Make it if you want to, take as long as you want, use whatever graphics you can - but simpler graphics will reduce development time.)
* The outcome shouldn't be decided too long before the game actually ends. This matters more if it's multiplayer - it can be fun to spend a while at the end of the game steamrolling over the AI, but it's not fun to get steamrolled over yourself for very long. (See also: "any game with >2 plyrs, 1 winner means >50% of your players will lose. Make losing fun.") This is hard to avoid in games with a big economic buildup.
* 4X games tend to be really long. If a game lasts several hours, by the end of a game you've made hundreds of decisions and it's impossible to tell which decisions were key to the outcome. A lot of these decisions are busy-work that doesn't have much effect, maybe giving small efficiencies. If a game is shorter and has less busy-work, it's easier to tell what you did wrong (or right), and therefore easier to improve your skills. (My personal preference is for games that can be played a few times in one session; this gives a really tight feedback loop for trying out different approaches.)
* Following a set "build" isn't interesting. Jasmine said up-thread to separate the players to give them space for an opening.. I don't agree with this. If you start out completely isolated, there will be one or more optimal openings, and (once the game is understood) the first few moves will just involve executing one of these; whereas if the players are interacting from turn 1 they have to adapt their strategies to the situation. (This can also be achieved by adding random elements - resource locations, power cards, etc.)
* It's nice if the different strategic options feel fundamentally different to each other. Building spaceships with lasers vs. spaceships with rockets is not a big difference. Diplomacy, covert ops, land grabs, high-tech research.. these can be quite different.
*
Opportunity cost. When you're balancing the cost of different actions, take into account the alternatives that an action precludes. Particularly relevant if you have a limited number of actions per turn, or there are mutually exclusive research paths.
* Randomness is interesting, and can be nice to introduce uncertainty and risk into actions. Also helps to avoid the first point (outcomes determined before game end) if there are high-risk options you can try in a desperate situation. Simultaneous blind decisions can substitute for randomness. It's nice if you have a chance of beating a more experienced player through luck - it's psychologically positive on both sides (you don't feel that it's futile to even bother playing, and they don't feel bad losing to a weaker player because they can blame it on luck).
* Recent board games have a lot of creative ideas for mechanics - play some of these and you might find useful things to borrow. In particular, a lot of them avoid player elimination (because it's no fun to be out of a game already when all of your friends are still playing!), which has interesting consequences: it requires more interesting victory conditions* than just "be the last one standing", and players must still have a chance of winning (otherwise they're effectively eliminated but still have to keep playing - even worse than elimination).
* Most of them use a point scoring system to determine the winner, but the means of gaining points are many and varied.