It depends which distro you use and how much stuff you want to put on it, for example a maximum install (RH or fedora) can take up to an hour. However A coustom/minimal install only takes Half an hour.
There isn't tons of stuff to setup unless you want to network it, even then it is simply A mater of pugging everything in, and if neccecarry do A little configuring.
As for your internet, sadly there are not many ISPs that support linux, which are you using? I know for a fact that bigpond doesn't support linux.
You want A full install of linux for your laptop? You'll have to download the .iso image to your machine then burn the .iso file to CD. After that put the linux CD in to the machine and go have A beer, in fact have a six pack and watch the grass grow.
In other words yes Linux will install over XP no problem, be carefull though if you want to convert a Linux machine Back to windows, it is tricky.
I recomend Ubuntu for any user, it is simple to install, uncluttered and has access to Root terminal. from reading your post this sounds like what your looking for. The disadvantage is it uses Gnome desktop environment
If you want A KDE environment try Kbuntu or fedora.
Or if you want to go for a more windowsesk type of environment try Xrandros or SUSE. Personally I would stay away from these if your going to use windows, use windows, if you want linux use linux.
A couple of links for you to try:
Ubuntu full and Live .iso images are here:
Kbuntu Live and full .iso images are here:
Hope this helps,