Dune II was definitely influenced by Herzog Zwei, but not everyone had a Genesis, and I don't think Herzog Zwei really had a concept of base management or resource gathering, which have obviously become integral to the RTS games today.
You're right, it wasn't like most RTS games we know today. Herzog Zwei had little bases scattered through the map that could be thought of as territories, and you'd have to capture them with troops(both the player and AI would compete for these as it allowed further expansion, healing, etc.). You could order up defensive / offensive units as "credits" trickled in over time at a fixed rate(I don't think there was any way to speed it up), and the ultimate goal was to send your assisting units to attack the enemy's single fortress.
I absolutely loved that game, though!
I don't really recall it having any story, though.
That sounds very much like the more modern DOS game Z: http://en.wikipedia.org/wiki/Z_(video_game). It eschewed the Dune 2 RTS mechanics that had already become dogma by then and I distinctly remember finding it refreshing. (I grew up on DOS so I didn't know anything about the Genesis).
