This song didn't begin as the nine minute opus it turned out to be. It actually began as two seperate songs: "Things Are OK In Oyster Bay" and "The Ballad Of Brenda And Eddie".

In the late 1970s Billy Joel had a little song called "The Ballad Of Brenda And Eddie" which was essentially the middle part of "Scenes From An Italian Restaurant":

Brenda and Eddie were the popular steadies
And the king and the queen of the prom
Riding around with the car top down and the radio on
Nobody looked any finer
Or was more of a hit at the Parkway Diner
We never knew we could want more than that out of life
Surely Brenda and Eddie would always know how to survive
etc.

The only problem Joel had with the piece was that it didn't have a beginning or an end. It was just a little story segment and he couldn't come up with a way to begin or end the song (musically, that is. Lyrically it was complete). Joel and his band would trot the song out at concerts and college tours just to see what kind of reaction it received. It was well liked, but Joel still wasn't happy with it. The piece went to the backburner.

Around the same time Joel had a "stupid little ditty" called "Things Are OK In Oyster Bay" which went a little something like this:

Things are OK In Oyster Bay
Me and Bob and meatball hero
Fishin' pole, onion roll
Take the boat out all day

While fun, it obviously wasn't album material. Joel kept it around, playing it for fun during his writing sessions, until one day he had an idea. He kept the "Oyster Bay" tune and reworked the lyrics...

Things are OK in Oyster Bay --> Things are OK with me these days
etc.

Suddenly there was a connection between "The Ballad Of Brenda And Eddie" and these new lyrics. The new section was about catching up on old times and talking about what had happened since the crazy days of yore. Joel combined it with "Ballad" and was happy with it, but still felt it needed more. He wanted musical bookends for the song; something that would wrap up the entire piece. Hungry, he took a break from writing and went to dinner at a local Italian restaurant. Sitting in the little hole-in-the-wall place and trying to think of how to bookend his new song, the waiter came to his table.

"Bottle of red?" the waiter said, "Bottle of white? Whatever kind of mood you're in tonight."

Joel jumped to his feet and shouted "Thank you!"

Back at the piano Joel put it all together: old friends meeting at an Italian restaurant to discuss old times (Brenda and Eddie) and catch up on new ones (Things are OK...).

If you've ever wondered why "Scenes From An Italian Restaurant" contains several different musical styles, then now you know. The song is actually a combination of several different pieces.

I'll meet you anytime you want in our Italian restaurant...


References:
Billy Joel told this story at a 1996 lecture appearance.