I agree, try before you buy, and if you post what your weighting requirements are, that might be useful. The special permit HP100 tanks, like the worthington X7 or faber FX100 are considered very versatile tanks that almost everyone loves. I wouldn't get a bigger one at this point unless you can find a seriously good deal. I also wouldn't worry too much about getting a 3442 PSI fill, these days, especially in southern Cal, you won't have any problem getting that.
Nitrox is a bit of a complication, because the rules and policies for filling tanks with nitrox change from shop to shop and maybe depending on the weather or if the tank filler has been gettin' any lately, who knows. The 'safe' (in terms of actually getting the fill) thing is to have the tank O2 cleaned, labeled, and only filled with nitrox or modified grade E air, which is the air used in nitrox blending.
Used tanks are the way to go IMO. I also like using the smallest and lightest tank I can for a given dive, which means that my local dives here in TX, which are very shallow, I like LP72s or AL63s the best. Maybe someday I'll get really nutso and start local diving with AL40s. So if you're talking about relatively shallow shore dives where you don't need tons of air, try picking up a few used LP72s, I'm sure there are tons of them around your area, or used AL63s.