The same thing happened with microprocessors. Early microprocessors didn't have enough space for microcode so they all had hard-wired control logic. It wasn't until the 8086 generation that you could put enough transistors on a chip to make microcode practical in a microprocessor. The 8087 co-processor is an interesting example. In order to fit the microcode onto the 8087 chip, Intel had to use weird semi-analog multi-sized transistors. This let them store 2 bits per transistor in the microcode ROJM.
Even today, I would be shocked if ARM designs weren't partially microcoded as well. Something like the ERET instruction is begging to be.
In short the ARFM has decode logic that makes a bunch of clocks worth of ALU controls directly, while the x86 has decode logic that makes an index into a ROM from where that information is read/generated
There’s two types of microcode: vertical (the kind people think of when hearing “microcode”) and horizontal (a large PLA). So, the 6502 is not “sort of” microcoded, it is microcoded, just horizontal microcode.
A better example of horizontal microcode (and what I learned on) are the PDP-11s. A clear micro instruction address counter and the ability to jump around the micro instruction ROM, but very wide control words where it's clear 'these three signals go into this mux, this signal is an enable over here, etc'.
[*] For standard definitions of microcode.
You could use a PLA to produce exactly the same outputs from the same inputs, but it wouldn't be microcode. The PLA is "just" an optimization. But with a PLA, you can't change a micro-instruction without ripping out some of the logic and replacing it. You have a hardware implementation rather than a software implementation, which is the hallmark of microcode. In other words, changing a control signal value in the 8086's microcode is trivial, but changing a control signal in the 6502 is considerably harder.
As a concrete example, the design of the Apollo Guidance Computer is clearly microcoded, with specific microinstructions. However, the implementation is gate logic that completely obscures the microcode design. (Not a ROM implemented with NOR gates, but highly-optimized logic.) So I consider the implementation of the AGC to not be microcode.
(This is kind of splitting hairs, and I'm not really into subtle linguistic arguments.)
Some small minicomputers like the PDP-8 in the 60s/70s were hardwired logic; they were so simple that microcode wasn't necessary to cheaply implement them. Along the same lines, some early microprocessors like the 6502 also weren't microcoded (though they still tended to use large ROM lookup tables driven by a custom state machine so sort of half-microcoded).
Some very large early supercomputers were also hardwired; the CDC 6000 series, Cray-1, or IBM's largest System/370 models, for example. Microcode was avoided to minimize the logic delay during a single cycle and get things running as fast as possible. The same philosophy would resurface in the 1980s with RISC. But then RISC chips started adding microcode back in to handle complex multi-step instructions, etc.
Nearly everything else has been microcoded: everything from 8-bit microcontrollers to the Motorola 68K to the VAX, later RISC designs like POWER and ARM, every iteration of x86, etc.