I am actually looking for exactly the same type of mod, and agree with you that increasing the tedious aspect of gameplay does not make the game harder, just less fun. I just started my second playthrough with the "fallout - new fps" that somebody recommended to me on a different forum:
http://newvegasnexus.com/downloads/file.php?id=34736
So far so good, but I'm not far from the start. If you've tried this one, let me know what you thought of it.
I gave that one a shot but it kind of kills the RPG elements of the game, armour, weapon and ammo choices all become a little trivial and HP and survivability remain virtually the same from level 1 to 30. I don't think the improvement in combat is worth sacrificing a huge chunk of the leveling curve.
Put on your Reinforced Chinese Stealth Armour and find some Deathclaws.

At this point I think that the only way to make the game more challenging is to enforce some RPing decisions. Try a non violent character, a melee tribal, a dandy who wants only the best suits and no crude weaponry or food... Possibilities are endless if you use your imagination.
The Perk every level mod is only game breaking if you powergame when picking your character's perks, if you go for some perks that are of minor use it won't be game breaking.
Likewise bobbleheads add points to stats but stats are not that important and the difference is probably not that huge -a minor boost to everything that's true but not as overpowered as some custom modded weapons or armours for instance.
IMO the Reinforced Chinese Stealth Armour is probably the thing that will break your game and make it too easy. My advice would be to lower its stats or edit it in some way as to make it useful but not too powerful.
No Fast Travel (and you don't need a mod for that) does make the game more difficult by the way (but it wil increase the number of encounters so it also means more XP). hardcoe mode is pointless when you use fast travel and teleport all over the map (something that is both cheesy and incredibly easy). No Vats is also a fun way to make the game more challenging (if you use vats in the first place of course).
Other than that my advice would be to try to RP a character that will do certain things and won't do other things depending on the background. I could think of a down on his luck gambler/scoundrel the blacksheep from a well off family who enlisted as a courier but really wants to get enough caps to enjoy the easy living he's grown accustomed to and who despite being broke won't do tasks that he deems to be beneath him... That's just an example. Playing such a character will probably make for a different game if not a more challenging one.
Look I know you're trying to help, and I do appreciate it, but I've said so many times that I'm looking for combat difficulty increases. Things that I'm definitely not interested in would be role playing, increasing hardcoe rates, walking everywhere, slowing down how fast you can travel between places, reducing the amount of stuff you can carry, increased radiation rates etc. Basically anything that concerned with "immersion" or "realism" probably isn't going to be what I'm after. None of these things make the game harder, unless you consider clicking a sink slightly more often difficult. You are no more likely to die with the arguable exception of walking everywhere, which does mean you have to fight more random things during the course of the game, but it's virtually always stuff you've killed previously. Repetition isn't a particularly exciting challenge for me.
What I'm after are mods like this ( ive only got working mods for the first two)
No Auto Aim
No healing food/drink
Increased AI reaction from stealth attacks
Soft leveled lists (random higher level spawns)
Increased spawn numbers
Slower stimpack healing
Increased damage from enemies with guns at higher levels(without increasing your damage vs them or making them drop more powerful weapons)
That kind of thing, stuff that makes it harder to kill and easier to die without just turning every enemy into a bullet sponge (they are already spongy enough) or putting the player in situations where they can be 1 shot killed as that realistic battle and combat dynamics mod does.