An interesting idea.... I guess the first thing that comes to mind is don't. Not because its been done, but because it was a bad idea to begin with. But I won't debate the pros and cons of sessions with you, so here is my answer...
Let's break this down by the 'type' of token:
Anyone can simply 'guess' one of these, yet they are fast and easy to use. Since the session is usually short-lived this is not generally a major problem. Also a great solution because they are small in size (22 bytes base64 encoded guid, or 32 bytes as hex)
You wrote: "I would be considering using something along the lines of a 512byte value generated by the RNGCryptoServiceProvider."
Yea OK it seems like 512 byte id's would be cool; however, even 128 bit values (16 bytes) have an absurd number of possibilities (more requests than your server can handle in a year). Don't make this your primary defense, instead assume that the id is not a secret.
- PKI Encrypted and signed data
This works well to 'hide' the information flowing through the transport. Do you need to? Is it worth the considerable overhead? There is also cost in the amount of data flowing in addition to computation/verification overhead. Is it more secure? probably, but in the end it's just as easy to steal as the random id.
Always assume someone else can obtain the session id/token
This is where you should focus your energy because if I can give someone else my cookie and my account is still safe, then and ONLY then is the session secured. That being said I don't know of a 100% way of doing this without client certificates, and even that has issues.
In the web request world there are two pieces of client identifiable information included with a request. The client IP address and the User-Agent. The problem is these values can change for a session. So an approach is to either re-prompt for verification every time these change, or for each distinct value.
Yes, I'm aware that a User-Agent is very easy to fake, and a client IP address can also be spoofed; however, at the end of the day you've made it harder for someone to attack. That is the point of security for nothing is absolutely secure.
More advice
For highly sensitive data you should timeout sessions quickly (< 5 min).
Obviously SSL is a must for numerous reasons
SSL has support for 'secure cookies' which are never written to disk or persisted. This can make the session id harder to obtain.
Key cycling can be used effectively enough, if you generate a new session key on each visit as Cris Lively suggests, you need to keep the last N number of session id's alive. So if N=5, after 5 requests my original session id is no longer valid.
Learn from others, read, and hack around on your existing accounts with other major sites.
finally...
I'll again say that sessions don't scale well and should be avoided in all but a very few places.
UPDATED:
So I've thought some about this since my last post, thought I'd update my thoughts with another answer...
Generating an id of 16 bytes or larger should be sufficient to effectively eliminate an attacker guessing session ids. Assuming this and the use of SSL + secure cookies you should be about as secure as you can be. Why?
SSL will effectively prevent someone from obtaining a session key during transit. Thus, if someone does have a session key that does not belong to them, it's because they are doing one of two things: A) they are running code on the client (maybe in the browser), or B) they are running code on your server. So basically if they can compromise an endpoint you've already lost the security game and their is likely to be very little gained by any additional work.
If your not using SSL, you have no security anyway. A simple man-in-the-middle attack will let an attacker do anything I want on the client's behalf. Any work to secure the use of HTTP without SSL (or some form of securely negotiated session key) is simply a pretense of security. Yes you can make it more difficult, but you can't make it secure.
So in the end, simply trust SSL to do it's job of securing the transport and get on with life :)