With the improved seek performance now implemented in dr_mp3, I ran some benchmarks.
opus seeks take < 0.4 ms, mp3 < 0.9 ms, wav and flac roughly 2 ms, and vorbis < 7 ms.
Given a 70fps game, that's 14ms per frame, so all of these codecs can complete the seek within a single frames' time, which is great.
Even though vorbis is still roughly an order of magnitude slower than opus and mp3, keep in mind PCM-exact seeking in vorbis is extremely difficult, as documented by Sean Barrett: http://nothings.org/stb_vorbis/ogg_seek.txt, who's the author of stb_vorbis. He later went onto offer a $5000 USD bounty for an efficient implementation - and eventually got it (https://github.com/nothings/stb/issues/117). So sub-7ms is still great.
I think the other good news is Opus is the clear leader - so the Xiph authors (https://github.com/xiph/opus/blob/master/AUTHORS) have solved more than just making a great quality/bitrate codec.
stb_vorbis
CDROM: seek(34485024) took 5.321646 ms
CDROM: seek(183027936) took 5.928965 ms
CDROM: seek(337883616) took 6.493050 ms
CDROM: seek(1759296) took 4.413499 ms
dr_mp3 pre-generated seekpoints, 1-every-10 mp3 frames
CDROM: seek(35574000) took 0.818466 ms
CDROM: seek(189785232) took 0.778496 ms
CDROM: seek(334329744) took 0.396842 ms
CDROM: seek(6115200) took 0.266457 ms
sdl_sound's WAV decoder
CDROM: seek(32165952) took 0.015657 ms
CDROM: seek(186301920) took 2.208570 ms
CDROM: seek(339344208) took 2.146041 ms
CDROM: seek(200296320) took 2.193242 ms
CDROM: seek(5268480) took 0.014133 ms
dr_flac pre-generated seekpoints, one every 1s of audio
CDROM: seek(29124816) took 2.617673 ms
CDROM: seek(189147840) took 2.730340 ms
CDROM: seek(336470064) took 2.725294 ms
CDROM: seek(1759296) took 0.343579 ms
xiph opus
CDROM: seek(35574000) took 0.332695 ms
CDROM: seek(189147840) took 0.356307 ms
CDROM: seek(333777024) took 0.365779 ms
CDROM: seek(5268480) took 0.238305 ms