I realized/found yesterday that in the Global.asax that there's a method available called "Session_Start". I believe that will work perfectly.
I could also use the Application_Request method, but I don't want to hit my SQL Server that often.
(I'm also thinking of adding it to the "Session_End" method in case they are on the site for along time...
Here's a link to the Global.asax methods available:
http://sandblogaspnet.blogspot.com/2008/03/methods-in-globalasax.html
Edit/Update:
I just stumbled across this article on CodeProject that appears to be the time that the cookie is ready:
http://www.codeproject.com/Articles/288631/Secure-ASP-NET-MVC-applications