I'm thinking about a map with hexagons, and with "edge". the edge will be a small graphics painted over the two tiles, at the limit between the tiles.
Put that out of your mind.
Hexagons don't allow movement in 8 directions, and all Civ3 units move in 8 directions. The only solution is to use squares. That doesn't mean that your terrain can't be interesting, however. Read on...
Also, I played at some point with a concept of height, where each tile could have a different height in addition to different terrain. But it makes things really complicated in term of map graphics, so i think it is not a good idea.
Or perhaps, it's not actually that difficult. Read
this discussion about
this graphic. The advantages that variable height terrain brings to gameplay is immeasurable: troops can conquer 'high' ground, submarines can dive deep, canyons can be traps, etc. etc.
Sim City 2000 (now
abandonware, by the way - the original Sim City source code
has now been released) used 2d iso terrain, combined with blocks stacked to create terrain (as seen
here). The advantage of this approach was that it allowed tunnels and underground improvements including subways and water pipe systems (a toggle allowed gamers to "see" the underground improvements under the terrain.
SimCity 3000 improved on that system, coloring and texturing the terrain to look more realistic, and added the innovation that an 8-bit bitmap could be used, not to determine terrain type, but rather terrain height (a very good description of how this worked can be found
here). This allowed
real-world maps to be used - which would make our war-scenario makers very happy indeed, I imagine.
I think it may be easier to get support with a solid gameplay but placeholder graphics, than with nice graphics but very shallow gameplay
Then there's CivII: Test of Time (in my opinion the best Civ engine yet built), which could simulate extreme heights and depths by using co-joined maps. This allowed underground, underwater, above-the-clouds (aerial combat), space, and alien planet maps all in the same game. Honestly, if gameplay, rather than graphics, were my primary concern I'd still be playing ToT rather than C3C.
If I were designing this all myself, I'd combine all of these ideas together. A map might have dimensions of, for instance, x=150 y=180 z=20, made entirely of isometric cubes with dimensions of, say, 127x64x64 pixels. Like ToT, three or four maps could be 'stacked', and a toggle would allow players to "see" down to the map below it (straight through any map containing 'Air' or 'Space' tiles).
Each cube type would have assignable properties:
Land cubes could be grassland, plains, polar, tundra, desert, tropical, swampy, marshy, rocky, hard rock (e.g. Granite), or soft rock (e.g., limestone or sandstone). These terrains could be made to change with seasons or eras. Seasons would only be available in games using monthly or weekly turns; Climate Change could affect games using longer timescales (e.g., one turn=25 years).
Underground terrain cubes might be: hard or soft rock, hard soil, soft soil, or sand. Resources wouldn't be visible until directly encountered.
Water tile cubes could be affected by depth (shallow, deep, very deep) and also temperature ('icy' which would slow ships, or 'ice', which would be impassable to ships, but suddenly passable to light land units). Some might be assigned as 'ocean currents', which would allow watercraft to move incrementally faster in a specific direction.
I would start with that. But I wouldn't end with that....