1. Update your software.
2. Use strong passwords, or public keys, for all accounts, regardless of how unimportant they seem. A strong password is one with letters, numbers, and possibly special characters, 8 or more characters in length, and is changed periodically.
3. Don't run unnecessary services or services with a poor recent security history.
Disabling the root login is a legit choice, though if someone figures out your sudo-capable account, you're equally screwed, so use strong passwords always.
Changing the ssh port only stops the people who aren't targeting you specifically, and even those people aren't always stopped. It is trivial to scan a host to find where ssh is running, regardless of the port you put it on.
fail2ban or denyhosts are OK for preventing brute force attacks, but OpenSSH and most security sensitive software already has timeouts, among other measures for preventing brute force attacks. Which makes fail2ban more of a nuisance-prevention measure (i.e. you see fewer brute force attacks show up in your log reports, and thus making it easier to see the more dangerous threats), rather than a core security measure.
If you performed your three steps, but ran an insecure version of any service (particularly those that have elevated privileges), you would still be easily exploited. fail2ban or denyhosts would prevent most services from being exploited due to weak passwords, so that's probably not a hole you'd have. And, changing the ssh port does nothing for you if your system hasn't been updated and is running exploitable services.
I used to do security cleanup and post-mortems and data recovery as a contractor for folks who'd had systems exploited. 90% of them were due to running old versions of software, and the rest were due to weak passwords (which may or may not have been prevented by fail2ban; in a couple of cases the exploiter used the webmail client to brute force the weak passwords...most people don't include the webmail client logs in their security considerations, and thus wouldn't configure fail2ban to ban attempts on the webmail client).
I'm not saying your advice is not useful, just that it's something you do after you get your core processes in order.
Edit: Formatting.