The extreme case of "how many relocations you have" is zero, which is position-independent code. The 8080 inconveniently uses absolute addresses rather than relative addresses in its call and jump instructions and doesn't have a PC-relative data addressing mode (or really much in the way of addressing modes at all; the Z80 is slightly better here). Lacking a PC-relative mode for one or the other means some base pointer register somewhere has to tell the module where it lives. On the 8080 or Z80 this would make your code super slow and bloated, particularly since statically allocating addresses to your data is such an important optimization there.
An intermediate case is "the linker relocates a global offset table". Without any kind of base address register this requires each GOT entry to be at a fixed memory address, so it has to be globally allocated across all the modules you're ever going to have loaded: one entry for every subroutine or global variable. Every call and global variable reference has to indirect through the GOT. For global variables this is also super painful on the 8080 because of the lack of indexed addressing. A nice plus, though, is that it makes it easy to unload a module, as long as the module isn't on the call stack or otherwise has its addresses stored someplace. This is useful both for having more code available to run than you have memory for, and for dynamically reloading code as you modify it.
The other extreme is the usual case for LINK.COM or ld(1): you have one relocation per callsite or global variable reference, so linking takes a long time, but there's no per-variable-reference or per-callsite overhead.
There's a similar set of options for when the linking happens. You can allocate all the static addresses during compilation, which avoids the need for a separate linking stage but also makes separate compilation impossible, which is pretty much a nonstarter for self-hosted development on 8-bit systems. You can allocate the static addresses when you build an executable, which is the standard LINK.COM/ld(1) approach. You can allocate them when the program starts, which is the current ld.so approach, and requires the linker to run at program startup. (You might automatically cache the thus-relocated version of each module so that future loads at the same address could be instant, but the floppies on 8-bit micros were both too small and too slow for this to be practical.) Or you can allocate them when the first reference to them is made, by initially pointing all the GOT entries at a trampoline function that passes control to the dynamic linker to resolve just that single GOT entry, which requires the linker to run throughout the lifetime of your program. (In theory you could do this without a GOT on a per-callsite basis, but I've never heard of anyone doing that.)
A scheme more common than runtime linking on 8-bit computers (and on pre-IBM-360 mainframes) was "overlays," which allowed you to have more code in your program than would fit in RAM, without slowing it down. You partition your program into a central core, which was always loaded, and two or more overlays, only one of which was loaded at a time. The overlays couldn't call each other, but they could call within themselves and to the central core with no overhead. When the main program wanted to call an overlay, it would have to first make sure that the overlay it was calling was the one that was currently loaded, and if not, load it from disk, which typically took several seconds. And overlay schemes could get more elaborate, with the possibility of having multiple overlays loaded at once, direct calls between overlays, and so forth. If you had multibanked memory you could load different overlays into different memory banks, and switching between banks was a lot faster than loading from floppy, but it wasn't nearly as convenient as just having a bigger memory space, even in the shitty 8086 segment:offset fashion.
I've been thinking a lot about reviving some of these recondite techniques for low-power computing. The Ambiq Apollo3 ARM Cortex-M4F chip costs US$5 and has 1MB Flash and 384K SRAM, and uses 33 pJ/instruction plus 68 μA overhead at 3.3 V. So you could run a 10-DMIPS "workstation", a hundred times as fast as a Z80 and comparable to a SPARCStation 2 or a 386/40, on 0.6 milliwatts, which is about the same as a solar calculator, and you can burst to much higher speeds (48 MHz, about 60 DMIPS) or run there all the time when you have direct sunlight. Another 0.05-0.2 milliwatts pays for a 400×240 SHARP LS027B7DH01A memory LCD. But 384K of RAM is pretty limiting, so you need some kind of virtual memory or overlay scheme. It doesn't have an MMU, but I think its MPU avoids the need for a trusted compiler scheme like HotSpot to prevent different tasks from corrupting each other. And of course ARM is good at indexed addressing, has lots of registers, and has position-independent jumps and calls by default.