The first "3-D" games I remember well were Atari's Night Driver, both in the arcade and on the 2600, and Radio Shack's Skiing, for the TRS-80 Color Computer.
Both games were very simple -- the 3-D effect was depicted using fenceposts or poles marking the outlines of the path. There was no lighting, shading, or environmental detail. Night Driver was played on a flat surface, with realistic curves but one glaring limitation -- the reason you were driving at night was that it was possible to render blocky white fenceposts against a black background; any other scenery was out of the question at the time. Skiing used more detailed flagpoles to mark the path and employed a nifty clipping effect to render horizontally-edged hills, but the snowy background was solid white, again to keep the level of detail manageable.
These early 3-D efforts were under serious constraints -- there were no polygons, and both were essentially 2-D games rendered from a 3-D perspective using a limited 2 or 4-color palette. The behind-the-scenes math went largely into creating an illusion of 3-D streaming from the background out of the screen; there was no way for the view to change perspectives, but there was tricky math and some data involved in presenting the curves and hills on display.
True 3-D came along (for me) with Atari's Battlezone and Star Wars arcade games, and Argonaut's Starglider on the Atari ST. (Yes, I missed out on Red Baron and Elite at the time.) These were vector-style games, with simple 3-D models rendered as clean lines against a black background. There were environments, rendered simply as matrices of dots and other shapes; no filled polygons yet, but the 3D-to-2D math was working properly and fast enough to render real-time animation to the flat plane of the screen. The player could travel, turn, and explore a world that felt remarkably solid, no matter how schematic its rending. These games were the true forerunners of today's 3-D -- there was no hardware-assisted filling, texturing or lighting, but the world was truly constructed in three dimensions.
Of course, lots of 3-D games fall somewhere in between complete fakery and true math-based virtual worlds. Space Harrier has a little bit of 3-D awareness to position objects in its game world, but renders that world using scaled sprites and color-cycling tricks. Sierra's King's Quest used height-based masking techniques to allow characters to walk behind and in front of 2-D scenery. Wolfenstein 3D is a 2D design rendered in 3D, with boxes rather than true polygons, and no lighting, but it has texturing and priority handling down pat, thanks to an innovative and speedy "ray-casting" technique. Early Playstation and N-64 games had texturing and lighting and true polygons, but often resorted to using 2-D sprites where more detail was desired and polygons could not be spared (see Twisted Metal's vehicle and course decorations, or Mario Kart 64's entire vehicles).
Lest I lose my retro street cred, let me reiterate that what matters, ultimately, is the game -- an illusion of 3-D that works is just as much fun as true 3-D. But there's a whole history to the technology involved, and now that 3-D is well and truly the standard, it's fun to look back at the techniques and cheats employed before we got here.