Most Veruca Salt fans also seem to have a soft spot for Letters to Cleo and othe radio stuff like Tracy Bonham.
While I'm not much of a fan of any of those, I would say that there are some excellent "girl rock" bands out there:
As mentioned above, Sleater-Kinney - which I also would say is probably one of the only interesting rock bands currently putting out records (boys or girls). Not quite as glossy pop as VEruca, but if you start with their most recent album (all hands on the bad one) and work backwards- you might like them.
The band Autoclave is also very very cool- (Mary from Helium with Christina Billotte from Slant 6- recorded way back in the early 90's. Way ahead of their time, and very cool). Again, more angular and mathy than Veruca, but interesting none the less.
I would also say you might like The Donnas- basically the ramones if they were girls (add in a slutty factor so that they're not intimidating or taken too seriously).
Liz Phair's first two albums (Exile in Guyville and Whipsmart) are excellent, but not really as pop-core as the Veruca Salt stuff.
Babes in Toyland- interesting suggestion- nothing like Veruca Salt- more vicious screaming noisy.
L7- if you're gonna add Babes in Toyland, I'd add L7. Although some argue if the singer even sounds like a girl-- more dirty LA street rock.
That Dog- I think the last that dog album before their breakup is one of the most underappreciated pure pop records I have ever heard. Why Mtv didn't play the shit out of this, I'll never know. Again, start with their last record (retreat for the sun) and work backwards. I think it you like Veruca, you'll love that dog.
Other Possibilities: Breeders, Amps, Kelly Deal 6000, Helium, Elastica, bis, pj harvey, velocity girl, lush, cibo matto, slant 6, quixotic, lois, cub, cakelike, lucious jackson, bjork.
And if you're really looking to broaden your horizons, try bikini kill, huggybear, heavens to betsy, Le Tigre, Julie Ruin, 7 year bitch, dickless, courtney love (the band not the girl), etc
Sounds like you might need someone to make you a mixtape
-Vince
NP: A mixtape I made for scott in my head
all the good ones are mentioned, but i don't think anyone recommended Concrete Blonde.
even though they're not techncially a girl-band, the lead singer can really rock. she has a scruffy, but not fatiguing (sp?) voice.
they have a great range...from the melancholy "tomorrow wendy" to the melodic "joey" to the hard-edged "still in hollywood" -- they're songs are as varied as you could ask for. i'd say their overall sound is pretty unique.
their best of compilation (i think it's called 'recollection') is a great sampler.
Along the lines of what Vince was suggesting for expanding your horizons would be the bands Fluffy and Teen Angels. Both of their albums are fairly difficult to find these days but make for interesting listening if you can track them down.
You also asked whether the earlier Veruca Salt albums are worthwhile. I certainly feel they are if you like Eight Arms To Hold You. The feel of all three is pretty similar although the third album had the Bob Rock production where the first two were not as polished on the production (in my opinion this is actually a plus though).
You should check out Nina Gordon, Tonight and the rest of my life CD. It is alot softer then when she was in Veruca Salt. It is still good non the less.
I will also add the recommendation for PJ Harvey, my second favorite artist of all time. And I will also recommend The Donnas, everything Vince said about them is so true
Sleater-Kinney are great rock n roll.
A new band you might want to check out are Pretty Girls Make Graves.