I've been looking into mics and I've heard that 3.5mm cables have problems with audio degradation over long distances. How long does the cable have to be before I start experiencing issues?
Like most things, it depends. There are several factors at play: the impedance of the source, the nature of the circuit (balanced vs unbalanced), the capacitance of the cable, etc.
Ideally you want a low impedance source driving a low-capacitance, balanced circuit.
The impedance of the source is a big factor. A low driving impedance will not be affected as much by higher capacitance (which increases with the length of the cable), so it preserves high frequencies better.
An unbalanced circuit is susceptible to interference like buzz and hum, and the longer the cable the more likely it is to pick up such interference.
A typical 3.5mm cable is unbalanced, so all things being equal it will not perform as well over a longer distance. How long? If there's a source of interference nearby, even three feet may be too much.
Jim did a nice job of getting to the gist of the problem.
As far as recommendations, If you are recording to a computer I recommend a USB mic. It converts the analog signal to a digital signal right at the mic, so after that you don't have to worry about interference at all. If you need extra distance, you can buy a USB extension cable and use that without worries of degrading your signal. I've used a decent Samson usb mic. Not for super high-resolution recording, but for the basics, it really does the job well.