Honestly for password encryption, you won't have the key storage issue if you use a one way hash and then instead of using the plaintext of the password, just hash user input and compare. The typical thing to use in C# is PBKDF2 (Rfc2898DeriveBytes). For other options see Crypto:What makes a hash function good for password hashing?
The key storage issue is always going to be difficult, DPAPI a pretty decent option it can protect the keys from other users on the same machine, and is much better than storing it in the DLL, but understand what it's doing, it's encrypting with the password hash of whatever windows user you are running (actually it's doing a lot more, key derivation, rotation etc from the password hash), and that's why you can't use the data encrypted from your local machine directly on the server. To use DPAPI, you will have to encrypt your key separately on each server (and that's not a bad thing).
It's always preferable not to hard code your key, not as much because it could be accessible, but because it's easier to change when you need to, or in different settings. Typically the most you can do without specialized hardware is just keep your key separate from your data. You can make things more difficult by encrypting the key, but you are just adding another key that an attacker would also have to get access to, there isn't an ideal solution.
If you want an easy way to be able to change your keys over time, I have ported the keyczar framework to c# it has the mechanisms needed to rotate keys so that you can still decrypt old data while encrypting new data, however it doesn't really offer anything more security wise in key storage accessibility.