There are some big changes to the way Fallout New Vegas works compared to Fallout 3. The basics are:
  • Level cap of 30
  • Perks given on even levels (every other level)
  • Lots of skill checks in quests
  • Some weapons have skill/strength reqs to use effectively

So, with that being said, here's what I think my next set of perks will be:
  • L2 Hunter (Survival 30) +75% critical damage vs animals (regular and mutated), useful early on due to the presence of ferocious (but cute) geckos, bloatflies, wild dogs and coyotes.
  • L4 Entomologist (Survival 45, INT 4) +50% vs mutated insects. You'll be wanting this the first time you meet a Cazador.
  • L6 Shotgun Surgeon (Guns 45) Subtracts 10 points from target's DT. This is massive for shotguns where the 20ga weapons are roughly 7x5.3dmg and 12ga are 7x8.5dmg. It allows you to effectively deal with all lower-level enemies that have armor using shotguns. Higher level enemies, you'll need to switch to slugs, but it still makes a big difference.
  • L8 Comprehension (INT 4) +1 point from reading skill books (4 pts instead of 3 pts), but the big benefit is that magazines (temporary boosts like chems) give +20 to the skill instead of +10, so you can use magazines to get past things like locked terminals or locks that need to be picked sooner. If you have a good supply of magazines, it means you can put off maxing out a skill like Science or Lockpick until late-game. It's a toss-up between Comprehension and Educated.
  • L10 Finesse +5% critical chance is probably the best choice. Or maybe Educated.
  • L12 Robotics Expert (Science 50) is +20% vs Robots, but there aren't many robots in New Vegas. A better choice might be Silent Running (AGI 6 Sneak 50) which allows you to crouch-run in sneak or Sniper (PER 6 AGI 6) which gives better chance of head shots in VATS. Long Haul (END 6 Barter 70) is a nice perk for traveling when encumbered, except that you'll usually have 1-2 companions with you anyway. If you sneak at all, go with Silent Running.
  • L14 Adamantium Skeleton reduces limb damage by 50%, which is a very important perk to have if you are playing in hardcore mode where limbs can only be fixed with Doctor Bags or by visiting a NPC doctor. Plus, the other L14 perks have very steep requirements, although Light Step (PER 6 AGI 6) can be very useful if you tend to be clumsy around traps.
  • L16 Better Criticals (PER 6 LCK 6) +50% damage from criticals. Or, if you rolled a low-strength character, go with Weapon Handling (STR < 10) which reduces STR requirements on weapons by 2 points.
  • L18 Backfill with Better Criticals
  • L20 Grim Reaper's Spirit restores 20 Action Points if the target dies in VATS. Or, go ahead and backfill with a more useful perk.
  • L22 Spray 'n Pray protects your companions from friendly fire. Useful, because you often have companions in-game in order to get their perk and quests; and they're always getting in your way.
  • L24 (backfill) No new perks here unless you are using unarmed combat, so go back and fill in.
  • L26 Nerves of Steel gives faster Action Point regeneration.
  • L28 (backfill) The perk here requires END 7, but is very useful.
  • L30 (backfill) No perks at 30, but you get to choose one last perk.

SPECIAL

So if we look at the list, we need:

STR 6 PER 6 END 5 CHA 5 INT 6 AGI 6 LCK 6

That's in order to use a very powerful rifle (the "AMR" which requires 8 STR, minus 2 points for having the perk) as well as being able to get all the perks that we picked out. However, at the start, you only get 40 points to spread among 7 attributes (5.71 avg). There are items (implants) that can be purchased later that can boost a particular attribute by one point though. The total number of implants is determined by your END stat (so you can have 5 implants with END 5). Given all that, I would go with:

STR 5 PER 7 END 5 CHA 5 INT 6 AGI 6 LCK 6
- Boost STR with implant
- NEMEAN Sub Dermal Armor, +4 to your DT
- Boost LCK with implant
- Boost PER with implant (and a hat)
- Boost AGI with implant

Bottom line, don't go below 5 for any primary SPECIAL stat. And the more that you can have at 6 to start, the better. The CHA stat is somewhat of a dump stat, except that your companions will be markedly better if you have average or better CHA. You can live with a stat at 3 or 4, it won't make or break you, but it's much easier if you stay at 5 or higher across the board.

It's a toss-up between PER at 7 to start and LCK at 7 to start. Go with Luck if you like to gamble as an eventual Luck of 8 (or 9 with the right outfit) can make a big difference at the tables in the casinos.

Skills

Skill points in New Vegas are few and far between compared to Fallout 3. Instead of (INT + 10) per level, you only get (INT/2 + 10) per level. The game will remember the half-point difference and will give you an extra point every other level. At the start, your skills will be in the 13-21 range depending on your SPECIAL stats. And probably more like 15-19 if you stayed with the "5 or higher" rule on your initial SPECIAL picks.

Education and Comprehension are then key skills for getting extra points when reading the (rare) skill books or when leveling up. Otherwise you'll only get 13 points per level (INT 6), boosted to 15 with Educated. Educated is the weaker of the two perks, but it's still equivalent to having 4 more points of INT.

Just like in Fallout 3, you get to tag (3) skills at the start. That being said, here's the minimums that you'll want early on (?? indicates no real minimum, unless you want to specialize in that weapon type):

25 Barter
?? Energy Weapons
25 Explosives
?? Guns (45 by L6 for Shotgun Surgeon)
25 Lockpick
?? Medicine
?? Melee
25 Repair
25 Science
?? Sneak (50 by L12 for Silent Running)
25 Speech
25 Survival (45 by L4 for Entomologist)
?? Unarmed

For your tagged skills at L1, I would focus on shoring up Barter, Explosives, and Speech *or* Sneak. If you want "Hunter", you need Survival to 30 before you level up to L2. Having Survival trained up early is also a big boon for hardcore mode players because it lets you make useful foods like Bloatfly Sliders.

Longer-term, Speech at 50 or 75 early on is very useful. There are a lot of things that are just easier if you have Speech at 50 (and then 75 at around level 20-ish). Barter at 50 as soon as you can get it there is useful for some other skill checks. Medicine and Science are also used, but not as often. You will run across level 50 and level 75 locks early on, so having Lockpick at 50 early will help. Locked terminals are not as common, however, so a Science skill that lags a bit is fine.

Explosives and your primary weapon skill are fine in the 30-40 range until level 20. You can compensate by using armor piercing rounds and buying better weapons. You'll want to slowly raise them up to closer to 50 by level 20-ish, however.