Security is always about making trade-offs. Just like the proverbial server which is in a safe, unplugged, at the bottom of the ocean, root would be most secure if there were no way to access it at all.
LD_PRELOAD and PATH attacks like those you describe assume that there is an attacker with access to your account already, or at least to your dotfiles. Sudo doesn't protect against that very well at all — if they have your password, after all, no need to try tricking you for later... they can just use sudo now.
It's important to consider what Sudo was designed for originally: delegation of specific commands (like those to manage printers) to "sub-administrators" (perhaps grad students in a lab) without giving away root completely. Using sudo to do everything is the most common use I see now, but it's not necessarily the problem the program was meant to solve (hence the ridiculously complicated config file syntax).
But, sudo-for-unrestricted-root does address another security problem: manageability of root passwords. At many organizations, these tend to be passed around like candy, written on whiteboards, and left the same forever. That leaves a big vulnerability, since revoking or changing access becomes a big production number. Even keeping track of what machine has what password is a challenge — let alone tracking who knows which one.
Remember that most "cyber-crime" comes from within. With the root password situation described, it's hard to track down who did what — something sudo with remote logging deals with pretty well.
On your home system, I think it's really more a matter of the convenience of not having to remember two passwords. It's probable that many people were simply setting them to be the same — or worse, setting them to be the same initially and then letting them get out of sync, leaving the root password to rot.
Using passwords at all for SSH is dangerous, since password-sniffing trojaned ssh daemons are put into place in something like 90% of the real-world system compromises I've seen. It's much better to use SSH keys, and this can be a workable system for remote root access as well.
But the problem there is now you've moved from password management to key management, and ssh keys aren't really very manageable. There's no way of restricting copies, and if someone does make a copy, they have all the attempts they want to brute-force the passphrase. You can make policy saying that keys must be stored on removable devices and only mounted when needed, but there's no way of enforcing that — and now you've introduced the possibility of a removable device getting lost or stolen.
The highest security is going to come through one-time keys or time/counter-based cryptographic tokens. These can be done in software, but tamper-resistant hardware is even better. In the open source world, there's WiKiD, YubiKey, or LinOTP, and of course there's also the proprietary heavyweight RSA SecurID. If you're in a medium-to-large organization, or even a security-conscious small one, I highly recommend looking into one of these approaches for administrative access.
It's probably overkill for home, though, where you don't really have the management hassles — as long as you follow sensible security practices.
