Security is not an absolute, a property possessed and evaluated in a vacuum. Rather, when you ask am I secure? the first response is against what threat model. You write:
I'm mostly only concerned about remote attacks from those who don't
know we have little worth stealing.
Fair enough, that's a good clarification. In that context, let's examine your other questions.
For sure the pubkey is very long, so a brute force attack is nearly
impossible, but, with a long password with strength enforcement (12+
chars, requiring all classes), isn't the likelihood of a brute force
attack succeeding already sufficiently remote?
You skate over the question of how you compel such complex passwords; there are a number of ways to change the password on a modern UNIX system, and you've assumed you can intercept all of them. One failure, one weak password, and your system is penetrated. But the main reason to prefer passwords in this context is that we see a large number of automated password guessers on the internet today. I am not aware of any attacks that currently try random private keys, and (barring further discoveries of systematic weak key generation) I don't expect to see any. Using keypairs moves you away from the attackers, and thus the attacks; there are bandwidth and CPU gains from this, as well as security ones.
With regard to key loggers potentially getting installed on a users
remote machine, why is that a greater danger than the pubkey being
lifted off of their hard drive?
To me, the issue with key loggers relates mostly to third-party machines, eg those in cybercafes. With password authentication, any user can log in from any machine, and some will; sooner or later, they will do this from a machine which is not trustworthy. It is possible to do this with public keys also, but to do so requires some skill, which is often accompanied by an improved risk awareness. Moreover, we see keyloggers in the wild; I don't think we've yet seen much malware that looks for keypairs on temporary local storage, then watches the network stream to see the remote endpoint(s) against which the keypair is used.
Another thing I've heard mentioned are concerns about a compromised
server stealing the users password.
None of this is happening in isolation. Password theft is useful to attackers because people often use the same password elsewhere. If your users really are required to have a 12-character password with strong requirements on choice, it is likely that at least some of them regard this as their "super sekrit" password, suitable for all the systems they're on that need a very strong one; your security is now only as strong as the worst-maintained system which is in that pool for all your users, and I for one am not wildly to keen to trust everyone else (which is why my own servers require keypair or hardware token + password for remote logins).
There are other secondary issues, eg keypairs being used in a transitive agent model, where logins from one remote system to another can be handled without sending private material "down the wire" to either, but hopefully the above analysis gives you some food for thought.
