I've already completed Fallout 1 once, but I would like opinions on a couple of traits. What's better for a brand new starting character? Finesse & Skilled, Small frame & Gifted, Small frame & Finesse or Skilled & Gifted?

Definitely take gifted. 7 stat points do make a difference and only a few skills are important.
Small frame is annoying and only acceptable if you abuse the unlimited carry capacity of party members.
Finesse is nice if don't score many non-critical hits, if you always aim at the eyes for example.
Skilled is good for unspoiled roleplayers who get a starting advantage and wouldn't take the most useful perks later, powergamers avoid it.

Since you're replaying just take whatever you like, I recommend trying finesse and gifted.

Personally?
Avoid Gifted. It's not like it's actually a problematic trait, but it channels you into whatever specific skills you take as Tag, or which can be increased by books to an acceptable level, and I found I overused it regardless. Simply, unless the raw stats are something you desperately need for some goal or another, I usually find Gifted isn't very fun.
Skilled, of course, also isn't any great shakes for other reasons.
Want higher stats with relatively little cost? Go Chem Reliant. That'll usually do the trick. Just take whatever you need for prerequisites, building around where and what you want to go and do later in the game, and be prepared to pop a few pills. Oh yes, and also be prepared to walk off the withdrawals.
But honestly, that's rarely been a problem in my opinion.