Fritzing in my opinion is awful. I just can't get the interface to work properly. Maybe it's just my computer, but I still don't use it.
Eagle has a really steep learning curve, but it was totally worth it. My first pcb was a pretty complex one, (my 8*16 rg led matrix display board with 6 595s and two uln2803s) and the only error was a stupid mistake and a product of laziness, I was too lazy to download an led matrix library, so I used two sets of female headers, but I swapped the top and bottom sets of headers! No huge problem, I just had to swap the nybbles of the byte for the shift register. Also, I used the autorouter, which I really thought was the best option for my purposes.
Go for Eagle, I would say!