This happened to me really early on and I had to do a colossal amount of work to get back on 'unfriendly' terms. Most of what people have said is true. The best advice is to find a federation aligned outpost but in a system that is controlled by someone else. If you stay in a federation controlled system then the constant interdictions will drive you round the bend.
A couple of rules I found out about the hard way:
Don't abandon any missions for them otherwise it will wipe all your good work,
Don't get caught smuggling as the resulting fine, even if it's tiny can cause your reputation to get even worse,
Bounty hunting, trading and cashing in exploration data will all help your reputation, but in tiny, tiny increments,
Do not go bounty hunting in a federation controlled sytem, the security ships have a high probability of just opening fire on you for no reason.
Do not, under any circumstances, try to help out a federation aligned faction in a conflict zone. If the feds are hostile towards you, even when you select their faction, all of the ships on both sides show as red and they will all open fire on you. Quickest death I have had in game.
Security ships are allowed to open fire on you even if you're not 'wanted'. Apparently if you're out of favour with them the federation security ships are allowed to openly ignore their own laws - sounds like you may have experienced this already.
They are clearly extremely emotionally sensitive and can change their minds about you in an instant so once you've improved your reputation ensure you play nicely with them after that, always send a birthday card, send flowers etc etc.
My advice would be to fly to a part of human populated space on the borders of the Federation - there will be plenty of independant systems and when you want a break from the mindnumbing need to find 5 units of fish etc. you can fly quickly into the empire/alliance and play normally for a while.
Oh and completing Federation navy missions does, or at least did help improve my reputation hugely in one go.
When my reputation improved there appeared to be no rhyme or reason to it as I hadn't done anything for a couple of days and had been out exploring. But suddenly they were just unfriendly, when I was in deep space - not well balanced people.
I'm still emotionally scarred by my experiences, if you end up the same way maybe use the forum as a support group.