As a counter data point for bounty difficulty, I'll state I'm not having any problem with them. I will pick the ones I think I can do with the fleet I have, so I don't always go after the highest bounty. I haven't needed to wait around for bounties to expire and refresh - always had something I could take.
I was, however, putting together what I consider close to an optimal fleet. Which includes doing loops through populated space black markets to buy what I need (i.e. Drovers, Herons) when I have the cash.
In iron man, at level 40, I've got a Legion, an Eagle, 4 Herons, a Drover, a Medusa, and Wolf (plus assorted logistics ships). This seems to be able to handle any current bounty, which vary from about 180k up to 300k a the moment. I've got a damaged Onslaught, Eagle, Drover, Hammerhead, and Medusa sitting in storage. Skills are Tech, Leadership and Combat focused. No Industry. 1 Combat ship officer, 5 carrier officers with full fighter skills. This was from a tutorial start.
I have been using heavy fighter compositions, with me in a direct combat ship on the way up. Wolf->Hammerhead (D)->Medusa->Eagle->Legion. Assorted Drovers, Herons, etc for the other fleet ships. Fighter heavy still seems optimal to me, although I think it is weaker than before. The leadership skill changes do matter and I think were in the right direction. Fighter composition for the fleet is Broadswords, Longbows and Daggers, while the Legion carries Broadswords and Warthogs.
Admittedly, I restarted 3 times early on in 0.8.1, but not due to bounty fleets, but rather random fights (come out into hyperspace right next to a large enemy fleet, seeing whether I could take that Pirate Armada in combat with another fleet, etc). Poor strategic decisions on my part. And its faster (and more fun for me) to restart fresh than try to recover from 2,000 credits a wayfarer and a kite. Its also possibly a habit from Rogue-like games. I will admit, with the bounties where they are, if I lost my fleet and had no backup ships, I'd probably just restart. Trying to take cruiser class ships in frigates is a bit much. And without industry skills, it'd probably take longer to put the fleet back together when compared to starting over and just working up the bounty fleets again.
I've lost a ship here and there (i.e. Condor (D), Kite, Drovers, an Eagle), but have made enough to restore or buy new.
There was a period where I was trying to get an Odyssey to salvage for testing and was going after those Tri-tachyon preferentially. Didn't succeed in getting one yet, but I wonder if that biased the difficulty on the way to where I am. I think the "Balanced" Odyssey under AI control even with an officer is the easiest capital to kill in actual fleet engagements. Either I would solo it in an Eagle or order a fighter strike and watch it pop. Its kinda funny when some default Eagle loadouts last longer against bombers, because they have a better shield tank buffer than the default Odyssey loadout.