My internet connection is a 384K SDSL line from SpeakEasy. While not the cheapest, they do not mind servers and support static IP addresses and Linux/Unix systems. One of my Debian boxes is acting as a NAT router for much of my home network.
Overall, I am quite impressed with Debian. Their online update system is superior to anything else I've ever used, including many commercial versions of unix. The install is only average, a bit better than Solaris. If you want to download a CD image, I recomend avoiding the mess called the "Pseudo-Image Kit" and just downloading the ISO. They're available on LinuxISO.org. If you have a decent internet connection, the first binary CD is probably all you need. Once a minimal system is installed, you can easily select what packages you want or upgrade to a later release with dselect or apt-get. 2.2r4 (aka Potato) is the current "Stable" release, best if you want reliablity and don't need the latest and greatest versions of various packages. Woody is "Testing", and has more features, but the reliabilty is less. At any point in time, there may be a couple of prolems you have to work around, so it's only about as stable as a fresh RedHat (non .0) release. Sid is "Unstable", and frequently has many minor and a few major problems. Packages that are in Sid for a couple of weeks with no major reported bugs are migrated to Testing. Upgrading between releases is easy.
Some of the software I've written is avaiable here.