That scene about made-up vulgar names. Every repetition of "Biggus Dickus" from Pontius Pilate who fails to get the "joke" sends the guards and the audience deeper into hysterics. The mention of what Dickus' wife is named is what makes even the most desperately-trying-to-keep-a-straight-face members (of both groups) collapse into paroxyms of laughter. And then later on, we find out that Biggus Dickus actually exists!
One of them, when Pilate is trying to provoke a reaction, makes the most hilarious little squeaking sound.
Gotta love how, even though it's Enforced Method Acting, both the remaining guards feebly shake their heads at the line "He has a wife, you know. You know what she's called?" One of the guards has a face that screams Oh Crap, as seen here
And when we finally meet him, Biggus Dickus is every bit the comic highlight that a Roman centurion with a name like that deserves to be.
The introduction of Eric Idle's "Not the messiah: He's a very naughty boy" featuring Mrs. BettyPalin.
The Mr. Big Nose scene at the beginning.
I'm surprised no one has mentioned the Three Wise Men going to see baby Brian by mistake.
One of the Wise Men: We were led by a star.
Brian's Mother: Led by a bottle, more like! Get out!
Spike Milligan's cameo in the scene when Brian's followers are schisming over whether the gourd or the shoe is more holy. Milligan stands in the middle, watching them with a bemused expression, until the whole crowd realises that Brian has gone and starts to belt after him. At which point Milligan's character decides to form a sect of his own:
Spike: [raises hands dramatically] Stop! Stop! [declaiming] He cometh to us, like the seed from the grain... [He stops, realises that nobody's there, looks slightly embarrassed and walks off]