If I'm flying along in my C-152 and I am trying to go in a straight line through the "center" of C airspace, but the controller tells me to remain clear, what should I do?
Well, the obvious answer is remain clear of the Class C airspace :-)
HOW you remain clear is entirely up to you - you can go over, under, or around - you just can't go through, and I think that's the more interesting part of your question.
Flying around the class C airspace is usually a safe choice (don't skim along the margins though - give it some reasonable breathing room), but as you've noted it could add a lot of time/fuel. You need to balance that with the time/fuel required to climb above the airspace, or the risks of flying under the airspace (mainly obstacles) to make your decision.
I'm going to use my local class C airspace as an example for an exercise in aeronautical decision making because conveniently there's a VOR you could hypothetically be circling while talking to approach, and an airport on the other side you might want to get to.
In our hypothetical example let's say you're circling Deer Park VOR (A
) at 2500 feet, and you want to cut through the Class C airspace to get to Brookhaven (B
), but approach isn't cooperating.

Click to embiggen.
I've got three options sketched out here - think about them, then hover over the spoiler boxes for my thinking on each of the three routes:
The dashed line through the center (the route you were hoping Approach would give you).
A straight line is the shortest distance between two points, but this straight line stinks: Since Approach wouldn't let you go through the class C airspace you're going to have to spiral-climb to 4200 feet or higher (5500 feet if you're playing by the hemispheric rule), and then when you get to the cut-out in the class C on the other side you're going to have to dive down to get to pattern altitude.
That doesn't seem safe, nor efficient to me, so let's toss that idea out the window.
The northern route under the class C airspace.
Simple enough, we'll split the difference between the ground (roughly sea level) and the floor of the airspace (1500 feet) and fly under the shelf at 1250 feet. Plenty of room above and below (if your altimeter is set right and you're any kind of decent pilot).
So this is the part where I confess that I'm a big ol' wuss and don't like to be close to the ground. It's like a porcupine, but with radio towers for quills (like the one I marked with a big OUCH - at 1250 feet there'd be less than 500 feet between my landing gear and the top of that tower).
I'm not happy with the obstacle clearance on this route (and while I could certainly rearrange the line a bit to avoid the obstacles I'm not going to because they serve my purpose) -- the northern route is out.
The southern route under the class C airspace.
Same idea as the northern route - descend to 1250 feet and fly under the shelf, but I like this route a whole lot better.
There are really great landmarks here ("Fly southeast toward the looped road, then go to the middle of the bay and stay between the two shore lines until you pass the bridge at Smith Point. At that point you'll see the airport off your left wing and can maneuver to enter the pattern.")
You're also over water, and we don't tend to have any radio towers sticking up out of the bay.
You'll need to watch out for traffic from Bayport, students practicing ground-reference maneuvers, and banner-tow planes in the summer, but that's just your basic everyday VFR "See and Avoid" situation.
This is probably the route I'd pick.