Well, I don't know what the lower limit is, but I recently inherited an 8-inch Celestron Schmidt-Cassegrain reflector from my grandfather (he was a physics professor). When pointed at Jupiter, it shows the cloud bands, moons, and their shadows quite nicely, although I have yet to see the Great Red Spot.
You probably need something with at least a 3" (about 70mm) aperture. The most important number for most stargazing equipment is really light-gathering power (ie, aperture diameter) more than magnification. Many advertisements aimed towards astronomy n00bs will gush over their product's maximum magnification power, but this number really means little if you can't resolve the details of what you're seeing. A high magnification with low light-gathering power will give you a large, blurry image.
The
8-inch Celestron I have would cost you about $1200 new, with tripod, equatorial mount, and lenses (the mount and a clock motor are necessary to keep objects within the field of view as the Earth turns - the motor is built into the C8). My C8 is from the late 70's and still works great, so if you can find a used one that has been well taken care of, you'd probably spend significantly less.
Prices fall pretty quickly as you decrease aperture size - looks like the 6-inch reflector by celestron is a little over half as much as the C8. If you are looking for something far cheaper, go for a simple refractor - these are generally in the neighborhood of $100 and I have read several books which are geared towards small (3"

refractors. I only have a more expensive 'scope because, as I said, it was an inheritance.
Light pollution also plays a role in resolution - if you live in a place with dark skies, you can probably get away with a smaller aperture.
Take everything I just posted with a big grain of salt, since I have only ever used one telescope. If you're really interested in shopping for a telescope, check out an astronomy forum like the one
here.
-----signature-----
One special advantage of the skeptical attitude of mind is that a man is never vexed to find that after all he has been in the wrong.
- William Osler