Yes, it is possible.
However, as others say, the standard Arduino won't do a great job, so you will need to get (or even design) a Shield card to do most of the work.
In that sense, the PC becomes a radio keypad, display, and speakers. The Shield card is the actual "Radio" and the Arduino is the interface between them.
So, what do you nned from your shield? It depends on what you want from the SDR.
A basic SDR is the "SoftRock" series. You plug in an antenna, send it a frequency over an I2C interface, and it spits out (over audio) a section of RF around the frequncy you specified. Relying on the Arduino to convert that will run up aginst the ADC limits mentioned. You a get a functional, but weak, radio. Note: the actual conversion of signals to audio will happen in the PC...
What if you have your own ADC? Yes, you can sample faster, and the Arduino acts like an external sound card. It pumps more signal to your PC, where fancy software steps in and selects a station from all the guff coming in.
You can do better - but here's where it gets REALLY challenging.
If you have a _Really Fast_ ADC you can sample at RF. Then you need something to cut it down, before you send it to the PC. We're talking DSP processor, or an FPGA chip.
This chip will do a FFT (Fourier Transform) on the RF. Presumably, the result gets shown on your PC. You pick a band of interest, and the Arduino tells the chip to throw away everything EXCEPT the bit around that band. Then the chip does an Inverse FFT, and the Arduino pipes that section to the PC for final decoding.
The Arduino becomes the USB interface to the ADC / FPGA. If that's what you want, there are better and cheaper USB interfaces out there. There may be some value to all this as a learning process, but I wouldn't consider it practical.