I recommend playing the hardest difficulty first. The game really isn't that much more difficult and the difficulty achievements stack. So when you finish the game in hardcore you'll get all three difficulty cheevos.
And as far as I've heard, no one has ever 100% completed the game. I've even read that you can't get 100% in the game due to some sort of glitch in the percentage tallying system, but I don't know the actual truth of that. Also having to search 400 square miles to find that one last thing you didn't blow up doesn't seem fun to me. Frankly 75% completion was more than enough.
Not that I didn't like the game, but yeah, it's seriously huge and, the longer you play it starts to take forever for the meter to move 1 percentage point.
Still a really under-rated game tho'. I think it's funny that I picked it up used at GameStop in like March of 2012 and it was $16.00, now it's $26.00. I wonder what happened there?
- Do the Stronghold missions. Not only are they super-fun, but they open places that you can fast travel to and be dropped off at all over the island. Many of which have vehicles such as helicopters with guns that make searching/destroying the island much easier.
As far as the enemies, are you using the grappling hook on them? Making sure you have a little cover and use the grappling hook liberally really helps take the enemies down.