And you set yourself up here. Take your "alicebob" password example. If you allow all-lower-case passwords an attacker trying concatenations of obvious words needs to try 4 possibilities to crack that password. OTOH if he knows you prohibit all-lower-case he only needs to try 3 since "alicebob" is illegal. You've just decreased the amount of time he needs by 25. That's significant. The fact that "alicebob" couldn't be used as a password is exactly why the attack is faster, it's a vulnerability and not a feature.
As far as passwords being replaced by "something better", I doubt there's anything better for the obvious reasons (eg. biometrics are unchangeable if breached and even more predictable than passwords since there's (in theory) only one possibility for a given user and knowing the user an attacker can determine what that sole possibility is). We'd be better-off sticking with passwords and looking at ways to remove the need to commit them to fallible human memory and enter them in error-prone ways like typing, which are probably the two greatest contributors to password vulnerability. #3 is very probably transmitting the password itself over the connection in order for the remote end to validate it, and we've had the methods to eliminate that for decades (all browsers support challenge-response authentication for instance, the only reason it wasn't used was because of IE6's brain-dead rules about which method to use if more than one was available).