Amarok fetches lyrics from online so if nobody has posted the lyrics of a song to the database, it can't be fetched.
Also you would be surprised how good lossy formats are these days. In a recent thread at Linux Audio Users mailing list, no-one was able to reliably pick mp3s encoded with LAME at 160kbs from lossless files in ABX testing. Personally I use FLAC or ogg Q7, both sound good.
SoundKonverter is a great tool for CD ripping, converting and Replay Gain. I find it a bit simpler than K3b, although K3b is the best burner anywhere.