There are a couple of things other than session state related thread agility that can cause long BeginRequest times.
If New Relic cannot get deep/detailed enough data into the transaction, it rolls it up into the BeginRequest method time. This can also occur if the time could be spent in the database or an external service. This is also demonstrated with asynchronous activity that cannot be tied back to the transaction that fired it.
There are also instances when the application is first started where you can see long BeginRequest times. For your Azure application, you can try turning your app pool's start mode to "Always On" to see cut down on times where your app might have to stop/start, causing long begin requests.
Here is a document that contains some additional information, and here is a forum post where users without session states have had similar issues.