Free codecs without patent issues were limited to things like Vorbis which never got wide support. There were FOSS codecs for patented algorithms, but those had legal issues in places that enforce software patents.
Pre-Spotify, MP3 players would usually only ship with MP3 support (thus the name), so people would only rip to MP3. Ask any millennial and most of them will never have heard of Ogg.
Pre-Spotify (and pre-iPod) there were plenty of cheap MP3 players that also supported Ogg Vorbis. I owned one, for example. Obviously MP3 was THE standard, but Vorbis reached a good adoption HW wise (basically because it was free as in beer to implement)
Have a look at audio hardware from 10-15 ago (so long after the mp3 player wave ended in first world countries) but basically everything that plays mp3 plays ogg vorbis as well.
There is a lot more audio codecs embedded in other things than there ever were personal music players, by orders of magnitude. Vorbis was ubiquitous in video games, for example.
Personal music players had the issue that they had to have MP3 due to market forces, so offering Vorbis didn't save them any money. There were also some design decisions in Vorbis that made it a little more annoying to support on some very limited hardware than MP3.
(I know nothing about the legal side of all this, just remembering the time period of Ubuntu circa 2005-2008).