In my opinion, the hard drive's like the third easiest laptop component to replace, especially in more recent laptop models (The first being the battery, the second being RAM on the condition that there isn't a module under the keyboard).

Since you're flat out replacing an internal hard drive, what would be a really nice thing to do is use something like Macrium Reflect or PING to make an image of your current hard drive, but you might need to already have an external hard drive to actually do that. That way, when you put your new hard drive in, you start up that program and restore from the image you created, so you don't have to reinstall the operating system or any programs you already have, everything from your old hard drive is now on your new hard drive and nothing needs to be reregistered, nothing needs to be updated, and you don't need to hunt down drivers or install disks. You can either expand the partition to take up the full drive from there on out, or just make a new partition with the remaining empty space, whatever floats your boat. Seriously, all you people saying reinstalling the OS is a pain? DO THAT. IT IS SO MUCH NICER AND IT IS FREE PROVIDED YOU ALREADY HAVE THE HARDWARE.

USB controllers are pretty much going to be slower than Hard Drive controllers, so yes, you're generally right in thinking that a USB drive would be slower than an internal hard drive.

What you need to know about your laptop is whether your internal hard drive is SATA (Serial ATA) or IDE (also called PATA, Parallel ATA). It probably isn't IDE unless it's a very old laptop, but it won't hurt to check. If you can't find anything in Device Manager or kin about what kind it is, Here's a picture. Do note that most companies like to have an additional connector in between the hard drive and the connecting board, so you might need to remove something. SATA connections are forwards/backwards compatible, so 3.0 Gbit drives are usually the norm for whatever drive you're buying.

For practical purposes, Hard Drives come in 5400 RPM or 7200 RPM speeds (there are also 10,000, 15,000, and other oddball RPM speeds, yes, but let's just pretend those don't exist, as well as Solid State Hard drives which are much faster, much more expensive, much more energy efficient, and usually have lower capacities). Difference between the two is slight and most consumers won't be able to tell the difference without running tests, but lower means slower read/write times but longer battery life. Bog standard is 7200, but lots of retailers sell 5400 to upsell battery life.

For brands... All hard drives are practically made from the same components. If you read reviews, no matter what company you look at, you will find lots of people complaining about fast-dying drives or dead on arrivals for anything that isn't Solid State (and even then!). Failures are over-reported, successes under-reported. Go with whoever offers you the longest warranty without costing extra. I usually prefer Seagate, because their non-refurbished stuff usually comes with 3 years but it is ultimately your responsibility to check this out for yourself- and I've had no troubles returning my one failed drive. Western Digital is often mentioned for this reason, too. I'm biased against "green" drives whose firmware shuts down the hard drive when not in use, because that functionality is typically built in to the OS you're using and I don't want any conflicts there.