First off - nice hat (Go Vols!).
And thanks, I already had a custom web part taking care of the cookies and it wasn't working quite the way I needed and that's why I was trying other things. What I found out through this process is that a web part's OnInit is fired after OnContentLoaded - not sure I would have guessed that as "Content Loaded" would seem to imply it was towards the end of the process.
I ended up moving all the cookie set up and checking code (in other web parts) to the OnInit method and all seems to be working well now. I did use the CookieHelper class as well as it simplified the code - it's affect on the actual timing issue I'm less sure of.
At the end of the day, what would be really nice to have is some kind of Kentico page life cycle (i.e. what events fire in what order). Does anyone know if this exists? I haven't found it yet.