Solera downtown has a patio, but a limited menu on the roof, and it is loud up there.
Lucia's in Uptown has patio/sidewalk seating.
You can sit outside at 20.21 in the Walker. Great view.
Azia on Eat Street has sidewalk seating and could be appropriate.
Masa is not 4 or 5 star really, but it's good and the buses don't run as heavily on Saturdays down Nicollet.
My recommendation: jP Bistro in Uptown. Ask for Andrew. Sidewalk seating, very good food, great winelist, special occassion appropriate, though it is a bit loud since you're on Lyndale.
I've had an "outdoor, 4 or 5 star fancy birthday dinner" at Osteria I Nonni in Lilydale. Excellent upscale Italian.
Muffuletta in St. Paul would be another option although it has been long enough since I've been there that I should stop publicly recommending it. There have been many, many raves recently though.
I'm having trouble hitting both "4 or 5 star", fancy and outdoor. I'm sure others will offer plenty.