Re: "Everything between sample points is lost"
Nope. Sampling includes filtering to get rid of the aliased copies. If it didn't, it would sound really, really horrible.
As other posters have pointed out, the filtering is never perfect, so sampling is never Nyquist-perfect either. Sampling at higher frequencies and higher bit depths should have fewer imperfections, although if the hardware is a bit pants anyway high-rate sampling won't make a huge difference. (And if it's really pants it can make the sound worse).
But the killer problem for digital is clock jitter. If the sampling clock isn't rock solid to nano-second precision, you can forget Nyquist, because Nyquist assumes perfect sample timing. A lot of the smeary-splashy-nasty sound digital used to be famous for was caused by cheap jittery clock sources.
If your DAC can accept an external clock, hooking up a studio-grade clock source will do the sound many favours. It will also make the differences between FLAC and MP3 more obvious.
IME I can hear the difference very clearly, and the MP3 sound is seriously fucking annoying, even in a car. But my gf, who is a classical musician and can pick out the notes in chords by ear, is fine with MP3s. She hears music as pitch lines and very fine timing details, and most timbres as a placeholder. MP3s include all the detail she needs.
In fact everyone hears differently anyway, because everyone's ears are a slightly different shape, so we all have different acoustic filters stuck to sides of our heads. So it's maybe not a surprise some people strongly prefer FLAC and others don't care.
Last point - CDs aren't really lossless. Because of dirt, scratches, laser servo issues and other inaccuracies, most players drop back to Level 1 error correction at least some of the time, so there's always some quality loss.
A good CD rip will be bit-perfect with multiple read passes made to minimise errors, so FLAC will always sound better. (I was amazed by the difference - so amazed I spent a few months ripping and selling off all my CDs.)