Yes, this was one they were giving in out command upgrade sims and it did trip a candidate I know up.
I think the old adage 'Fly the aircraft' springs to mind, the 737 dosen't turn into a pumpkin because the FMC fails but it's pretty disorientating when all these amber flags on the ND appear and you're back to pitch and power like a -200.
In our command upgrade, the airport was using RNAV SIDs, and in one of the little notes that most people brush over is 'In the event of RNAV failure, advise approach immediately' or words to that effect. Sure advise ATC, if you start flying all over the sky, they will start asking questions putting you under more pressure, advise them and request radar climb out, and go back to flying the aircraft. Clean up and run through the QRH. DODAR.
You can still continue under vectors or ground based navaids. You can do a CAT III with no FMC. I don't see any urgency in returning to the airport of departure, as you're gonna have to set everything manually, so why not at destination AD than departure. Obviously, it does depend on where your flying to duration, ATC etc.
MK