My character is level 10 and twice now I've been declined when I wanted to accept a quest. The sheriff in Redding and Lil Jesus in New Reno both said I wasn't strong enough when I wanted to do work for them.
Am I not a high enough level, or is my strength stat too low (it's 5)?

You need STR 6 (or be a woman willing to sleep with him) to get a job from Lil Jesus. You have to be level 10+ to do the sheriff's quests in Redding. It's actually pretty unusual for there to be requirements to ACCEPT a quest, though. More often your stats will influence the outcome but not actually prevent you from getting it in the first place. The two quests you've listed are the only ones I can think of, besides the Porn Star thing (which isn't really a quest).

So just chew some buffout for Jesus and go back to Redding later.

Thanks for the quick reply. Even though I'm already level 10, the Redding sheriff isn't giving me any options to ask for work, like he did when I was a lower level (and told me I was too weak). Is this a glitch or something?

Probably. F2 is full of dialog bugs.. it wouldn't surprise me if there was a level < 10 option and a level > 10 option but nothing in between. It's also possible that it's messed up because you talked to him too early. I'd suggest coming back at level 11 to see if he says anything else.

There's also an extremely comprehensive walkthrough for it [url=http://user.tninet.se/~jyg699a/fallout2.html]here[/url], which details what the various skill and stat requirements are for the various things through the game. It's worth looking at, but just stick to the character development section if you don't want to spoil everything.

That's awesome, thanks for all the information. That link looks to be really helpful too.