I'm a new player (with a party of new players) and we're about to hit level 4.  My DM decided to be a bro and let us get the stat increase and take a feat, at least this time (my first character died 3 sessions in, we kind of suck). For my new character I went with a fallen Aasimar OoV paladin.  My stats are 16,10, 12, 8, 13, 16 and my fighting style is great weapon fighting. Not really sure how to proceed, as there are like 60 feats.  Help a brother out?

Common feats to choose would be

Polearm Master - bonus action attack option - opportunity attack when creature moves into your reach

Great Weapon Master - option to take -5 to hit with +10 damage - bonus action attack option when you kill something

I'd personally go for Polearm Master first and Great Weapon Master later. Since you already have the great weapon fighting style I am guessing you are using two handed weapons anyway and both of these feats fit that playstyle.

Will Polearm Master work for me even though I use a maul for my weapon and not a Polearm? Also, thanks.

There are a number of great feats that work well for the Vengeance Paladin, depending on what you and your party are looking for:

1. Sentinel: Sentinel is a great feat thematically to keep your enemies close to you. Vengeance Paladins are all about getting to your enemies as quickly as possible and not letting them leave until they are dead. Sentinel does all that, allowing you to almost always get an attack of opportunity on an enemy, even if they Disengage... and if you hit they stay next to you. It's great.
2. Great Weapon Master: This one is particularly great against swarms of low AC enemies that try to use their numbers over their durability, or large baddies that just use lots of HPs instead of high AC. Also, being able to use your bonus action to take another hit if you score a critical or reduce a creature to 0 HPs is great against swarms as well.
3. Polearm Master: As someone already said, this is a good one as well, but it would require a change in your current character's tactics (since he currently doesn't wield a Polearm), so might not work from a role-play perspective.
4. Mage Slayer: Want to be particularly good at seeking vengeance against spell casters? Mage Slayer does just that. Become the bane of all spell casters.
5. Lucky: Any feat that lets you re-roll results is a good one. Flavorful wise it might not fit your character though.
6. Heavy Armor Master: This one is a more defensive option, but still a good one. It increases your Strength by 1 and reduces the amount of damage you take from non-magical bludgeoning, piercing and slashing damage. Good for survive-ability, though late game having your damage reduced by 3 is not as great.

If you're allowed the Aasimar racial feat Angelic Protection is excellent giving advantage on saving throws against spells and other magical effects.  The others mentioned are all excellent as well. 

FWIW you should just check this guide, it's fantastic and discusses feats at length (and even provides some example builds at the end).

http://www.enworld.org/forum/showthread.php?474035-GUIDE-My-Word-Is-My-Sword-The-Paladin-Guide

Edit: I think they suggest Variant Human as the only way to do the full Polearm Master build, so you should probably just stick with GWM + Resilient (Con) at 8 (i.e. basically the Half-Orc OoV GWM build).

 HA! I got you beat. Was knocked out twice in the first session... Actually I guess that isn't a good thing...
My paladin is currently lvl 1 with stats of 15, 10, 14, 10, 12, 15, is scourge Aasimar, and I plan to take him into a Vengeance Oath because of his backstory. He also uses a longsword and shield because of how I plan to play him, so the feats i'm choosing wouldn't work for your character but I would also like some imput as this is my first campaign and 2 deaths in the first session doesn't look to good for my well being. I do also have some questions related to the Sentinel feat which I will get to in its listing. Also, is there any reason to not take just feats? I get that it will let you put points into levels but the feats seem to be really good and outweigh the cost of 2 skill points because of what they offer via their mechanics. 
Feats I plan on taking for my Paladin is: 

Alert: gives +5 to Initiative (I hit first). Can't be surprised while conscious (for the role play experience, hopefully will let me save my team in interesting situations). Other chreatures don't gain advantage on attack rolls against me as a result of being hidden (plays back into the "Can't be surprised while conscious" side of the feat). The intent is for this to allow me to enter the front line and pull aggro by hitting first and let me follow up with opportunity attacks. 

Heavy Armor Master: Lets me deflect blows that would kill allies (For obvious reasons). Increases strength score by 1. Reduces damage from non magic weapons by 3 (also obvious reasons. This is intended to let me absorb more damage and keep my allies from getting hit so they can dish out damage. 

And now Sentinel (Thx for bringing it up Grizzlebub): which lts me drop a creature's speed to 0 for the rest of the turn. Lets me use an opportunity attack even if they use disengage. And lets me react to hit them if they attack someone other then me while within my range. 

Questions related to Sentinel: It indicates that I am able to take an opportunity attack or a reaction when certain factors are met (Leave my range or attack someone else) how often does this let me attack? Can I make an opportunity attack multiple times before it gets back to my turn or only once? 

Ex: We needed to create a fight to find a camp so we needed a trail, to get it we needed a point to start. Via the information we had, these bandits wouldn't attack a group larger then themselves, so I volunteered to act as a single person bait to draw out a fight. This put me in a 1v4 encounter with my allies lying in wait behind me with ranged weapons to provide support fire. It was our DM's first time as well so as the first bandit that I had swung at and missed left my range I took an opportunity attack and got real lucky instakilling him. He didn't move another out of my range till I died fearing an additional Opportunity attack, but he did have one pull out his bow and start shooting at my cleric while he was standing right beside me. Say both of them moved in the same turn without using disengage, can I make an opportunity attack on both of them with/without the Sentinel feat? I do plan on continuing this type of combat mostly because with the way our party ended up being set up, it will actually make everyone the most effective (one of our players couldn't play with us for reasons and he was the other big guy that would be front lining with me, so I have the most HP and AC on the team and I would rather my team stay alive so they can focus on killing quick so I can survive). 

It does seem like this would be a bit op though. I would be swinging at everyone that moved around me. 

Feats are nice but bumping your stats also has distinct advantages mostly on your ability to hit things and do damage.  Currently you're only getting +2 to both with 15 Str.  Same on your spells since your Cha is also 15.  While you will get small bumps to these from your proficiency bonus going up it's only one point and far less often.  

Heavy armor master tends to be really good early and then the longer you go it begins to be less effective as your health pool grows.  

You are allowed one reaction per round so just the one opportunity attack. 

Quote from TBdaBoss >>

I'm a new player (with a party of new players) and we're about to hit level 4.  My DM decided to be a bro and let us get the stat increase and take a feat, at least this time (my first character died 3 sessions in, we kind of suck). For my new character I went with a fallen Aasimar OoV paladin.  My stats are 16,10, 12, 8, 13, 16 and my fighting style is great weapon fighting. Not really sure how to proceed, as there are like 60 feats.  Help a brother out?

Quote from TBdaBoss >>

I'm a new player (with a party of new players) and we're about to hit level 4.  My DM decided to be a bro and let us get the stat increase and take a feat, at least this time (my first character died 3 sessions in, we kind of suck). For my new character I went with a fallen Aasimar OoV paladin.  My stats are 16,10, 12, 8, 13, 16 and my fighting style is great weapon fighting. Not really sure how to proceed, as there are like 60 feats.  Help a brother out?