Is there a tabletop game similar to Dominions? I'm looking for a grognardy army-level strategy game of armies with spells or abilities that have really strange effects or complex interactions.
It is not at all what you are looking for but D&D 3.X is actually really similar to Dominions in the way the magic system works. Spells are similarly bullshit with enormous "fuck you" effects.
Nation Wars is a game that originated from this board and was developed into a few less freeform spinoffs that saw some traction on mythweavers. They had plenty of common ground; a regionalized map (usually hex-based) with terrain and sites, regular and specialist troops (both more and less customisable due to the tabletop nature of the game) and multiple 'agents' or named characters who could oversee actions and provide them with bonuses to success or progress who would usually be relevant in one or two areas like administration, spying, battle etc