Does a public key absolutely need to be used to initiate an encrypted session?
First recommendation: Don't invent your own protocol, but use an existing one. Use SSL/TLS, in the newest version possible if you don't have to provide downwards compatibility to existing clients. This will take care of most problems here, you simply put in a pair of plaintext data streams, and get a pair of encrypted streams. There are TLS implementations for most programming languages available, I'm quite sure that .NET has one, too.
TLS is quite flexible about the key exchange, authentication and encryption algorithms (bundled together as &quot;cipher suite&quot;). You'll have a public key for the server (usually with a certificate, whose subscribing key can already be embedded in the client application), and then use (for example) Diffie-Hellman key exchange with public-key authentication. There are also password-based key exchange algorithms, then you even don't need a public key (but client and server need some other way to first get the common password).
To your questions:

SSL/TLS works fine with a constant public key, not a different one per-client. Of course, if the private key gets leaked, all future connections are broken. If you did use the simple &quot;encrypt session key by public key&quot; model (RSA key exchange), also all past connections can be decrypted. Diffie-Hellman provides forward-secrecy, as the key is generated from random input of both sides, and the public key is only used for authentication.
If you create a new key pair per-client, you'll need some way of the client to tell its name (or key ID or similar) before the actual connection.

I have no data about how long key generation nowadays takes, sorry. You also have to take care of having enough entropy for your keys. But as said before, there is no need to generate new keys regularly.

Instead of doing this yourself, have a look on the secure remote password protocol for generating a shared session key authenticated by a password. This is also available (standardized) as a key exchange method for TLS, though I'm not sure if it is supported by .NET's implementation.

You can use whatever cipher you want, but as said by others, AES is actually more likely to be secure than other ciphers. Also, modern processors have actually AES-instructions build in, which could make the performance difference quite small or even negative (i.e. AES-128 could be faster than CAST-128), if you use a library which actually can make use of these.