I've always played in campaigns where leveling occured during some form of downtime, so it's never been a problem. The only time I've ever not done that was at a critical juncture in a game. One PC had gone to -13, and ressurection simply wasn't available to them. Now, they had been right on the edge of a level before the session started and they had already had seven or eight tough encounters so it was not unreasonable that he would have leveled before that point; he got his 8 HP from the level and was suddenly at -5. Yeah, cheesy, but it prevented a major hiccup in the session and the campaign at the time.
I'd give everyone but wizards their new spells right away. Wizards generally have to have some quiet time to write their new 'realizations' in their spell books. The divine casters would generally have to wait for downtime before really realizing they could do this, but if they were in extermis, they'd suddenly know that they had an extra spell and it probably would be what they needed at the time. One of the little perks of being divine caster in my campagn is that, rarely, you'll do your prayers and preperations and such... and suddenly be struck with the insight that you really, really should take, say, Detect Undead.