Yep, same here, and then you're way overpowered before you're even halfway through, so there's little to no challenge.
This is probably my main complaint.
BUT, I think I've found a pretty good solution for that. It involves some self-limitations, but ones that I really think brings some challenge and involvement.
The biggest one is you do NOT unlock the last weapon holster. Limit yourself to 3 weapons, Far Cry 2-style. You still typically can cover your bases but you have to make more of a choice of what sort of loadout you want to bring. Whereas with 4 weapons, you can usually just stick to one set loadout and have something for any situation, limiting yourself by just the one weapon will usually make for far more interesting choices when you're sat at the vendor screen wondering what to bring. Its fun to mix and match different sorts of weapons and see how it affects how you approach missions or objectives. This change single handedly makes the game a lot better, in my opinion.
The next one is no fast travel. Granted, I've only unlocked about half the map so far, so I don't typically have to go from one edge of the map to the other, but if I do have to travel a long distance, I sometimes look at what I can do on the way. Or if there's nothing, then I try and find the nearest minichopper or hang glider. I try and stay and foot quite a bit, and while animal attacks can be pretty ferocious at times, it does keep you on edge. The world is just so beautiful that I think it adds a lot spending time on foot and taking in the sights and sounds.
Another one is tackle the fortresses solo. Even when they're still Very Hard. The first one I did, I felt I was probably making a mistake even trying, but it turned out to be one of the most enjoyable experiences of the whole game. I only got one of the alarms before hell broke loose and ended up dealing with 3 helicopters all total with no rocket launcher or 50 cal or anything and a seriously dwindling supply of ammo(I relied on having to loot corpses to take down the last one). Was pretty nuts.
Also, don't rush the unlocks in general. Especially the crafting ones. I never really went totally out of my way to hunt down animals to get as many of the craftable upgrades right away. I just kind of went about by business and unlocked stuff at a pretty leisurely rate. I made an exception for the inventory upgrade as it was frustrating to run out of space every 5 minutes.
My last big change was turning off markings and the minimap. Marking enemies isn't necessary to succeed and turning off minimap means you have to rely on sense of direction and your environment more.
After all this, the game becomes far more immersive and
rewarding. It feels like a worthy successor to Far Cry 2 while still having many of the improvements made with Far Cry 3.
ne; two; three; or four in a fortress. If you screw up and set off the alarm, let the guards kill you and start over. 
