I am interested in single board computers, and am currently wondering what you would recommend based on these criteria. (Before anyone says, none of the Raspberry Pi models fit.)

Requirements:
* Low power. In particular, it must be possible to power it from a type-A USB 2.0 port on a computer, which limits the power requirement to 500mA, if I understand it correctly. (The RPi 4 fails this requrement.)
* Must have device-side USB support, so that it can act as a serial or ethernet device, for example.
* CPU must support hardware virtualization. (This is where the RPi Zero fails.)
* RAM should be at least 512 megabytes, and the device must support at least this amount of storage.
* I would prefer a smaller device, like the RPi Zero.
* This device needs to actually be available, and it must be possible to purchase a quantity of 1.

Non-requirements:
* Video out is not required, nor do I need a GPU.
* The CPU does not need to be fast; a slower CPU that uses less power might actually be preferable here.
* I don't actually need GPIO.
* The architecture doesn't matter too much, as long as it supports Linux and the KVM hypervisor.

So, any ideas?

I found this site that has a database search that allows you to input the specs you are looking for in a SBC and then it will give recommendations, should help narrow it down

https://www.hackerboards.com/home.php

Amiga 1200
Olivetti Prodest PC1

I think I've seen this before, and unfortunately, it has some omissions. In particular, there's no way to search based off the specific modes of the USB ports (host, device, or OTG), which is important because I am specifically interested in devices that support device (or OTG) mode.

Also, it doesn't weed out microcontrollers, like those with ARM Cortex-M CPUs, which I consider to be a different class of device entirely. (In particular, microcontrollers can't run Linux, and I'm not aware of any with hardware virtualization support.) Those don't qualify, as they're ancient in the computing world. In particular, no USB and the specs aren't good enough to support Linux (one of those has RAM measured in *kilo*bytes, which makes it more like a microcontroller in that sense).

Those are likely higher end than what I am looking at.

Plus, higher end means more power consumption, particularly when it comes to CPU, which would likely preclude it from running under 500mA USB power.

I bet there's a way to get the RPis to work in USB device mode through the GPIO pins.

The Zero and the A models can work as a device (for the A, use an A-to-A USB cable, which is not supposed to exist per the spec, and which could cause damage if used when it shouldn't be), as can the 4 (via the USB-C port), but that doesn't really fit my requirements. The problems are:
* Zero and Zero W don't have hardware virtualization, nor does the 1A or 1A+.
* The 2 and later have power requirements that are too high, and at least the BCM2836 board Pi 2's have an issue that makes it hard to get KVM working.
* The issue with the 4 is, of course, the need for power, and I believe the only computer ports that could supply enough power are those with USB-C power delivery, which I don't have. (Ideally, I'd like to be able to use my Android phone, thich I believe has only USB 2 (OTG) so it needs to use low power, plus there's concerns about the phone's battery draining too fast if the attached device takes too much power.)

(I have been able to get KVM to work on the RPi 4, and I have used my phone to power a RPi Zero (haven't tried the W yet) and an Adafruit Pybadge (which is a microcontroller with screen and buttons, so not the same class of device).)

Not sure if this will help you but it is another data base but it appears to be much more in depth on search criteria including power (power min on the search is 800mW)

https://www.digikey.com/products/en/embedded-computers/single-board-computers-sbcs/933

One option is to use your Raspi4 or better yet, the Raspi3 (if it fits the other needs) over USB 2.0 underclocked. It is simple and pretty straight foward to do and, never tried with the 4 though, the 3b+ can work pretty well over USB 2.0 if not doing any demanding task.
There are some websites with good tips to lower Raspi's power consumption.

If you want I can try to power the Raspi 3b+ (only one I have available at the moment) by USB2.0, underclocked and running any CPU benchmark to see where it goes.

Edit: couple of links I had in my bookmarks about Raspberry's power consumption:
http://freneticrapport.blogspot.com/2013/01/raspberry-pi-model-b-to-model.html
https://www.jeffgeerling.com/blogs/jeff-geerling/raspberry-pi-zero-conserve-energy

What about an Intel Compute Stick? It should check all the boxes but the power one.

If possible you should try power the RPI powered by your USB port, I have a ancient fully overclocked RPI 1 B that works just fine hooked to a USB port of an also ancient LCD TV.