"For some reason I always got the impression that California hikes tend to be crowded, so I've been staying a bit east of there."
That depends on where you hike, and also which pass you choose to enter over, particularly on the East Side. The popular East Side passes, like Bishop, Piute, Cottonwood/New Army, Kearsarge, to name a few, will likely be crowded because they offer relatively easy access to some very pretty country. Others, like Taboose, Shepherd, and Sawmill are fairly strenuous, and as a result see a lot less traffic. If you are reasonably fit, and not overly sensitive to altitude, I'd recommend going in over Taboose and hike up into Upper Basin, then over to Bench Lake for a nice 5 day trip. You could easily extend it to 7-9 days by using two cars or a car/shuttle to position a car at the Sawmill Pass TH. then you could exit by following the JMT over Pinchot Pass to the Sawmill Pass turnoff and hike out over Sawmill Pass. This would allow you to spend a layover day up around gorgeous Woods Lake. That route would give you a great introduction to some of the Sierra's finest country without worrying about crowds except along the JMT. Even there it's not all that bad early in the season. Bench Lake has a lot of large fish and is not crowded. PM me for details if this kind of trip interests you. To get an idea of the scenery, check out the pictures in the two trip report links below. Start with day 7 of the second report for an idea of what you will see on the JMT over Pinchot and the Woods Lake/Sawmill Pass section of the trip. Ignore the "prose", as it is boring.
Taboose Pass/Bench Lake
http://www.backpackinglight.com/cgi-bin/backpackinglight/forums/thread_display.html?forum_thread_id=92440
Woods Lake/Sawmill Pass exit
http://www.backpackinglight.com/cgi-bin/backpackinglight/forums/thread_display.html?forum_thread_id=83051
Another good 8-9 day trip would be to go in over Cottonwood Pass to Miter Basin, then over Crabtree Pass to Crabtree Lakes, the JMT to the Tyndall Creek trail, and out over Shepherd Pass. Again, you will see some spectacular country. The southern Sierra is, IMO, the most beautiful part of the entire range. This route would offer an opportunity for easy side trips to Wallace Lake and Wright Lakes Basins, both of which I highly recommend. Wallace has a lot of very large fish, and smaller ones in Wallace Creek and at the outlet. Again, 2 cars or a car shuttle would be needed.
I could give you many more recommendations, but this should be enough to find out if you might be interested in a Sierra trip.
I haven't gone in from the West Side in many years, precisely because the trails start lower and are more crowded.
"And, of course, it's California…
That last was just for you. :)"
Of course. ;0)) Let it be noted I moved out of California 30 years ago, probably for some of the reasons you entertain. But the Sierra has continued to draw me back year after year. It's that good. IMO, of course.
You're SOL regarding permits. They're required everywhere. Taboose should not be a problem. Cottonwood is popular, but a lot of permits are issued, and early in the season should be easy.