So the first thing I thought was, well low-scale speed of light giving wonky graphics is both cool and help getting the feel of relativity, but what about some Homeworld or a Master of Orion type of game with relativity ingrained inside the game rules and mechanics? Probably the music sounding Homeworld-esque helped.
Consider a turn-based game: a turn being irrevocably discrete and the same for all players, each entity, depending on its relative speed - hence time dilation/compression ratio - would get a different number of action points to spend each turn. You can globally compute each item action points because you're simulating the game universe.
You can extend this to virtually continuous time by compressing/dilating time depending on the player's relative reference frame, and then you could cap the flow of time so that min_flow=real_time or max_flow=real_time, or even mean_flow=real_time. I could see this becoming a problem for say, a FPS game where the player would feel relativity as time slows down or goes faster, but for a much more global game applying such a scheme would make him witness each unit/planet/whatever relative reference frame time dilations/contractions from a sort of god-like reference frame. In a single player scenario (where you don't need base time flow synchronicity between players) this god-player could even change his own reference frame by scaling his base time flow between say min_flow and max_flow.
Try modelling the twin paradox that way, for instance...