What are the most secure-yet-convenient ways of creating a wallet, that require just remembering a password?
Take a password.
Hash it with SHA.
Use the hash as a private address.
Generate your public address from that private address.


Guess this would be the easiest algorithm for having a deterministic wallet. One could easily make a web service or a program to generate those addresses, but people generally don't trust third party services like this.

EDIT:
StrongCoin allows one to generate a private key from any sentence, and given that they encrypt the private key before your browser sends it out, one can trust them not to know it. Then, you can decrypt the private key (as far as I know, also on your machine), and import it wherever one needs (provided you don't want to keep your coins online). It is a small workaround, but seems to fulfil your friends' needs.