A very broad question, so a random dump of thoughts:
Elite approximates solid objects through convex objects. Because every game object (other than the missile) is convex that means by definition that every hypothetical ray of vision from your eye to the object other than generate edge cases must pass through it exactly twice: once through a front face and once through a back. So just eliminating the back faces makes any single object appear to be solid when set on its own against a black background. Back-face culling is a standard technique that remains in use as it cuts the work for any closed object, but in Elite the further requirement of object convexity helps to give the illusion of solidness.
Elite and many other games also use split-precision arithmetic. Individual objects are small but in a much larger space. So objects themselves have local geometry stored in 8 bits and rotated using 8-bit arithmetic. The object centre exists in a 16-bit (or larger) space and is subject to 16-bit arithmetic. Having located the centre in 16-bit space, sign extend and add the 8-bit results to get all intermediate results in 16-bit while having saved a lot on arithmetic. There are cheap and compact lookup-table approaches for 8-bit multiplication based on 8-bit lookup tables and simple addition so the saving is very substantial.
Plain vector games like Elite often do partial screen updates essentially by accident. It's too expensive to clear a whole frame buffer or to keep a spare and lines very rarely overlap. So they XOR objects in and then XOR them out again. As and when they can't keep up with the output frame rate, which is usually, that has the effect that objects across the screen are updated sequentially. When the screen becomes full you can see one move, then the next, then the next, etc.
Even as early as I, Of the Mask, animated scenes were being prerendered and replayed as a sequence of 2d draw calls, with some sprites added on top for gameplay. This presages interactive movies by about a decade.
Rescue on Fractalus probably begins the line for games based on a voxel heightmap, and does what it does on an Atari by leaving most of the surface details very implicit. It's drawing verticals of a uniform colour and just putting pixels on top because it's cheap to update a vertical of one height to another, and the pixels although sparse are enough to fire the imagination. Later games like Commanche could afford whole-buffer updates.
It might not be immediately obvious, but the 8-bit versions of Stunt Car Racer also assume they're filling a vertical space for faster solid graphics. They do not allow the car to roll beyond a certain amount, and when it does you can see the area underneath the track soft of rotate with you. So it's not really filling polygons so much as maintaining a 1d height map.
As almost everybody knows, Wolfenstein's optimisations are (i) to restrict walls to a single height and vertical location, collapsing the problem of drawing from 3d to 2d; and (ii) requiring them to be on grid boundaries, for a simple per-column test without prior knowledge. Restriction (i) also makes each column a line of constant depth. Which means no per-pixel divides. The limited number of potential outcomes also allows all per-column possibilities to be precomputed.
Doom keeps similar per-pixel optimisations for wall rasterisation but completely replaces the logic as to what should be drawn by using a structure called a binary-space partition ('BSP') tree that allows a very fast back-to-front sorting of level geometry and ensures geometry is arranged in advance so that sorting by depth is always sufficient for a correct drawing. Allowing geometry not to overlap vertically further collapses the amount of work necessary to decide which bits of walls remain visible after having sorted them.
Quake does a similar thing with a BSP tree but adds an additional structure for broad-phase elimination of sections of the world called a potentially-visible set. A side effect of putting a structure into a BSP tree is that you end up with a bunch of convex sectors that the player can stand in. Quake keeps a compact list in each sector of which other sectors could be visible. That allows huge parts of the BSP traversing and therefore of span comparison to be skipped entirely.
Games like Descent go a different way with convex sectors, rendering from that which the camera is in outwards and clipping each further sector to the portion of the display still unfilled by closer sectors. That's full-fat portal rendering: the surfaces that join sectors are 'portals' and the portals are the be all and end all for scene graph traversal and for visibility. Later but still retro games often use portals in a less strict manner as merely a broad phase for whether a section of the map might possibly be visible, particularly if they have a GPU that can report something like 'if I were to draw that polygon, [some/none] pixels would be drawn'. Games still do that, but I'm aware of it being implemented at least as far back as Mario 64 and twenty years passes my test for retro.
A different branch of games going back at least to Alone in the Dark prerenders the background and simply superimposes the moving objects. Some knowledge of the full-scene geometry is retained for collisions and clipping but most isn't retained at runtime. In Alone in the Dark pixel artists created the backgrounds. In Resident Evil they were CG rendered.
Little Big Adventure II is probably the most interesting branch of that system of thinking: it has the full 3d geometry of its outdoor world but presents it through fixed cameras. Each time the camera changes it pre-renders the background with depth information, after which only the main characters are redrawn in realtime. That causes a 0.5 second lag when changing camera, but that alone isn't jarring for the genre.
The Microsoft Talisman project from the mid-'90s tried something very close to what you're asking. It would start by rendering a frame as a sequence of tiles and submitting those to the GPU. It would approximate the next frame and possibly the one after that by having the GPU simply manipulate the original tiles based on the camera difference — rotate them, move them around, scale them, all of them independently of each other. Then when the CPU had prepared the next entirely-new frame, it would submit it. So you got perfect key frames plus approximate intermediaries. It was implemented and previewed, but missed its window for success as the ordinary 3d accelerators appeared on the market.
EDIT: also suddenly returning from the back of my the memory, a special word for Parsoft Interactive and the line of flight simulators up to 1996's 'A-10 Cuba!'. They were software developers that started on the Mac in the late-'80s, which means a massive display compared to processing ability. So they used a system of per-scan frame differencing to publish only the differences. Imagine a big green polygon that's rotating. The centre essentially remains the same so if you can figure how to redraw only the edges in less time than it takes just to redraw the centre then that's a win. Exactly how they did it seems to be vague but I'll bet it's just a matter of inserting spans into a structure that you can then traverse in x order (probably O(log n)) and performing a linear differencing of this frame and the previous at the end (in O(n)).
That's almost certainly why they were still pushing solid colour polygons as late as 1996, but also why they could do a pretty good frame rate at 1024x768x8bpp on a 68040, and a fantastic frame rate at 1280x1024 on my unaccelerated Pentium of 1996. Which was the best the monitor could display.