I just finished playing the first level of the game. I already want to start over to try different tactics.
Since this is my time playing through the game I'm open to suggestions.

What are the best skills to upgrade at the start of the game?
Are there any weapons I should avoid using?
Does a non lethal approach earn me more skill points?

Those are the first three questions that come to mind. I welcome any other nuggets of wisdom veteran players have to offer.

EDIT: It is worth noting that I have Deus Ex v2.0, New Vision, and the Project HDTP/Project HDTP beta releases installed.

I think your first playthrough should be mod free. I'm not saying mods are bad but you should experience the core game one time and perhaps enjoy the mods even more for what they are doing the second time around.

You don't have much experience to invest when you start a new game but it is a good time to get some basics down. I often start with one point in swimming, lockpicking and/or electronics. This is really all you need for these skills because one point in swimming is enogh to explore all the underwater passages and as for lockpicks and multitools, you will be carrying about 20 around most of the game.

Many people like hacking and will go for one point in computers and max out at two levels early in the game (the last level is wastefully expensive)

The only skill well worth maxing out is Rifles because it gives great bonuses to the best weapons in the game (assault rifle, combat shotgun and sniper rifle).. Pistols are fine at one level, as is melee (stealth attacks from behind usually kill outright anyways). Explosives play such a small role in the game you really should not need to invest in them. Heavy weapons too play such a small role in the game but can be fun to dump points into, or at least upgrade once to increase walking speed if you want to actually use them for something other than "opening" doors.

Lastly, there is medicine and environmental training. Both of these are quite redundant because there are so many other better options for healing, turning invisible and soaking up bullets. Then again, they are cheap so you can probably afford one level.

Besides for making hacking and guns much better, skill points aren't very important in this game. It is with nano-augmentations that you REALLY build your character and define a playstyle.

Weapons to avoid? Don't go around bashing and slashing people in the face because almost everyone in the game will shoot back and kill you with a single headshot at that range. Also, heavy weapons are quite pants for actual combat. The sawn off shotgun is quite bad too because of the ridiculously short range (the return fire will be aimed at your face as with melee weapons). If you want to shoot your way through the game, an assault rifle or combat shotgun is what you want. This game is not a shooter however, so you might want to consider playstyle options before deciding on weapons...

The game goes out of it's way in the first level to teach you that the non-lethal way is the most silent (which is completely illogical in a real world sense) but the game stops caring about enemy casualties after this level. The game does not award non-lethal takedowns in any way. What it does however is award stealthy play. Avoid conflict altogether by finding hidden passages like air ducts and locked doors. This nets you some minor experience points but more importantly some encounters will impact how other characters react to you. It is not a bad idea to go play it as stealthy as you can and only using non-lethal takedowns because incidentally they are the most silent (even a baton to the back of the head is more quiet than a knife, somehow).

The game is actually very easy on all difficulty settings if you go for all-out stealth. The difficulty settings only make combat more difficult by making enemies more accurate and damaging. Because of the wonky shooting mechanics in the game, it feels a lot better to play it as a stealth infiltration game where you only shoot at unsuspecting enemies or knock them out with a blow to the back with a melee weapon of choice.

I, for one, have played the game thrice through without mods and been more than happy with it. I found I would get low on lockpicks and multitools if I didn't have at least two levels in each skill by the midgame.
I've never bothered with Swimming. I haven't challenged the conventional wisdom that Swimming is a crap skill in Deus Ex. Keeping one rebreather around and using it at the end, not beginning, of your lung capacity tends to be all you need. However, see my footnote! Seconded. I have sometimes maxed out hacking just because I wanted to, but no other reason to speak of. This actually comes down to playstyle. I've played through with melee and relevant weapons and been very happy with my lethal options, but was only able to reliably deal nonlethal damage with pistols. In the late game, though, relying on pistols often requires some very fancy effort in order to avoid combat, or at least to avoid direct combat. More importantly re: melee, though, you'll eventually have a weapon which renders this the single most reliable damage-dealing skill of the lot, being far faster and cheaper than heavy weapons. It can even be used to open doors almost as effectively as explosives, and far more quietly and safely.
Okay, so it doesn't SOUND quiet subjectively, but I've found melee is usually a safe way to open things up. Seconded. I might recommend pistols and heavy weapons. The pistols should be useful through 2/3rds of the game, and the heavy weapons will become more plentiful and effective down the road. This is untested, though, and is simply the best I can come up with to render heavy weapons useful, 'cause dammit, rifles really do rock. Rifles and heavy weapons? Even if you invest in both, you'll rely on rifles too much to enjoy the flamethrower or Guided Explosive Projectile Gun you can't carry. They are, however, functionally mutually exclusive with their respective cybernetic options, particularly environmental training, hazmat suits, and environmental protection cybernetics, or same training, ballistic armor, and the nano-augmentation of bulletproofing. They simply don't stack well. Both true and untrue of the melee approach, since a strong melee build requires the cybernetics which are best-suited to dealing direct physical damage and also allow you to get close enough against tough, well-armed opponents. That's where nano-augmented bulletproof skin comes in. Late game, I'd be more worried about enemies wielding explosives or poison, and there are nano-augmentations for those as well. See my footnote below. I'll take his word for it. I've yet to give them their proper try. See above re: melee and nano-augmentations. Myself, I found the shotgun was lethal to its user mainly because of noise and reload time. Damage output was okay, and range wasn't a problem for me. Nevertheless, best save the shotgun shells for the assault shotgun. Note these both use the Rifles skill. Au contraire, it can be quite the shooter if you want it to be. I felt awful for it, but my bodycount with an assault rifle was tremendous. See that mysterious footnote... It notices from time to time, actually. Besides, the game's story and content actually push nonlethal takedowns for other and far more interesting reasons. You might find the game compels you... to feel. Nor does it reward lethal takedowns in any way, because: ...which feel awesome to get, by the way... Bonk.
It's true, the game does reward stealth quite often, and some of the people you will meet will pressure you either to kill 'em all, or to use that lighter touch and do the least harm.
Among the rewards of stealthy gameplay, though, is getting to know your friends and foes better. They talk to each other. They sometimes are very interesting and educational. Stop, listen. There's so much there. In a game so steeped in information technology, it's no coincidence how much you can intercept only by word of mouth. Eh, headshots with an assault rifle or mini-crossbow are oddly satisfying as well, though there's nothing quite as disturbing as finding a good perch and taking down your opponents with a sniper rifle one after another like some kind of classified Charles Whitman.

Footnote:
Don't be afraid to try something! Stealthy gameplay doesn't necessarily require a nanoaugmentation for stealthy running. It may be just as useful and fun to take the nanoaugmentation which grants you the ability to jump high and land safely, since that can put you well above the fray. If you want to try melee only with found objects, such as metal boxes, try it! If you want to redirect enemy AIs by throwing darts at the wall or putting up walls of crates, try it!
Don't be afraid to try something, 'cause you never know! You can climb the walls by jumping atop explosives you've clipped to it. If it's not too high, you can even jump back down and collect them again.

In an emergency (or if you just want to save lockpicks/multitools) the rocket launcher doubles as a lockpick for lockers and so on.

I think you may be reading my post as way more absolute than I intended it. I actually don't follow my own advice much because I always go for style over min-maxing, and more importantly: NO SAVE SCUMMING. This game and all others where character customisation is an important game mechanic plays VERY differently in Iron Man mode where you can not backtrack to 15 seconds ago before you accidentally triggered the alarm or got shot in the arm. All those skills deemed useless by min-maxing FAQ writers.might be seen in a new light.

By the way, one point in swimming is not for lung capacity (the rebreather fixes that) but for swimming speed.

Fair enough. I certainly considered any tips for a first playthrough incomplete without a statement about exploration, though, since I've found few games which rewarded it in quite so interesting a manner. Oi. I'm bad enough at these games, I just don't think I could do iron man. It must be frightful for atmosphere and well worth the trouble, though. In my experience, swimming speed and lung capacity have the same general benefit.

What do you think of the pistol/heavy combo? Think it'd work? As I said, I haven't tried it, nor done the math.

Thank you all for your advice. I selected training in Computers, Electronics and Lock Picking. I'm currently trying to retrieve the Ambrosia vaccine. Do you return to the UNATCO base after each mission?

I have encountered a small problem. I keep running out of lock picks. Is there anyone I can access at this point that sells them?

There are no dedicated vendors like in most modern games.

If you're running out of lockpicks this early, you must be using them everywhere. Here's a slightly-meta suggestion. When you come to a locked door, pull out your key ring and try to use it. If you just get a "it's locked" message, you need to either pick it, blow it up, or get around it. If your key ring animation goes off, and you get the "don't have the right code" message, you can find a key for that door somewhere.

You need to be a bit more thoughtful about using resources in this game. Just because your path is blocked by an obvious locked door it does not mean you're expected to pick the lock. There is almost always an alternative route. If you insist on lockpicking every locked door and container in the game, then perhaps you DO need to go for Advanced or Master lockpicking, but if you are more economically inclined you will find all the lockpicks you will ever need to get by with Trained lockpicking.

If you come across a locked door or an interesting looking container, don't immediately get to work on it with a disposable lockpick. Sometimes it is possible to stack crates and climb over walls or into windows, open the lock remotely by tampering with a switch or computer, and much of the time it is simply appropriate to smash or blow them open.

As for containers, they rarely contain particularly valuable items. The designers obviously loved littering the levels with locked containers which, once lockpicked, reveal a single multitool or a biocell. Ammo, lockpicks, multitools and medpacks /and soy food, and cigarettes, and alcohol...) can be found just about everywhere in the game. The stuff you really want to look out for are Nano-augmentation canisters, Upgrade canisters and weapon mods. These are usually hidden in tougher places than a locker or a footlocker. Safes and sunken ships are among the early treasure troves you are going to find in the game.

Have as a general rule that if you have to choose between picking the locks or blowing them open with those handful of grenades you're carrying around, go for the explosives first. This is especially true if you find a room full of simple locked containers.

If the door is weak, you might try meleeing it to its destruction. You usually won't miss the door later. This option serves one well in early parts of the game, and in the mid- to late-game portions it can work nicely with a specific melee weapon in your hands. Holding such a device, though, takes up about a rifle's worth of inventory and is most useful to those well-trained in melee weapons.

Will I be able to return to Liberty Island after shutting down the EMP generator?

Yes.

Ah. Well, be warned that it might not be there when you get back. Stuff changes a bit each time you return, so I don't know if the canister will remain.

If this is the first augmentation found at the top of the statue of liberty, don't fret it if you can't find it the next time you visit the office. You will find another one just like it later in the game, and even then the augmentations in it are not all that great. Remember that all augmentations are ACTIVE powers, which means you need to activate them when you want to use them. They drain power so you can't leave them running indefinitely. Most Augs have rather trivial effects to begin with so chances are you won't ever use them, especially as a first time player.

Missing out on an Augmentation canister is not that big of a deal. It is much more painful to miss out of UPGRADE CANISTERS because you need them to make most Augs even remotely useful, and they are quite rare. I think you can reasonably only expect to max out a couple of Augs by the end of the game with most others in their basic form or just one level of upgrades.

The first Aug canister you found in the statue of liberty has a choice of two different augs. One of them is almost completely pointless while the other requires an upgrade or two before it really becomes useful. The bad one is the one that increases melee damage. While it sounds good in theory, bumping up a 10 damage attack to 13 damage isn't going to make much of a difference if we assume your target has 30-40 hit points. Most weapons in the game deal fairly weak damage to all parts of the body, except for the head which is almost always instantly lethal. Similarly, melee attacks to the back of an unsuspecting (out of combat) enemy are instantly lethal with most if not all melee weapons. If you were supposed to fight long boss battles against durable monsters the damage increase from the Combat Strength aug would make sense. This doesn't happen in the game however so it doesn't actually make any real difference in actual game play. There is one exception though: Doors have a strength threshold which the melee or explosive attack needs to exceed in order to damage it. Mind you, the Combat Aug needs upgrade canisters to reach meaningful damage bonuses and there really are better ways to open tough doors other than temporarily boosting melee damage. It's easy to think "I'm a melee guy, i'm going for all the melee upgrades". I consider myself a melee guy at heart, but I still never take this aug because it doesn't give you an ACTUAL melee benefit. You don't need more damage, you need augs that help you apply your melee attacks and survive the return fire.

The better aug is the (from my memory) Microfibral Muscle one. Being able to push and eventually lift heavy crates does open up alternative routes and enable goofy but inventive solutions to channeling your enemies or blocking their paths. Gamey and nonsensical, absolutely, but fun. I still don't think it is worth more than a single upgrade canister and I only choose it because Combat Strength is worse.