I vaguely recall that Vorbis requires a fair bit more processing to decompress, enough to be a potential issue 15 years ago, but on modern computers it's barely detectable and doesn't effect performance at all.
My recollection matches yours. I remember loading a custom firmware on my iPod, around 2005. Vorbis support was a big new feature; they'd just figured out how to get decode working fast enough on its 80MHz ARM7 CPU.
Probably Rockbox? iPods their clickwheel interface and it's software was amazing for the time, but other MP3 players generally had kinda icky interfaces. Rockbox fixed that :)
The "fast enough Vorbis" was likely the addition of Tremor, the first fixed-point Vorbis implementation. There's a nice (but with many old entries) chart of decode speeds here: https://www.rockbox.org/wiki/CodecPerformanceComparison
On newer hardware + software, like the Clip Zip, the gap is much smaller and the performance way higher than needed in any case (except for HE-AAC, the clear loser).
MP3 almost always has hardware decode which is really power efficient. This isn't as bad nowadays since audio decode isn't that intensive relative to keeping your WiFi on.
Wifi might be 100-200 milliwatts, but a laptop's speakers are likely to be 500-3000 milliwatts. Headphones are likely to be about the same as the wifi, but can vary wildly.
Bluetooth speakers/headphones change that dynamic slightly; the amp+required battery ends up on the receiving end, so you just have to figure what the Bluetooth stream itself costs.
