Maybe instead of closing the accounts you will consider trying to have the fees waived? I don't think they will consider waiving the fees permanently, but it is worth the shot.
I am not sure what bank issued the cards w/ the annual fees, but the other option would be to do a product change to another card without annual fee w/ the same bank. This way you would keep your account history and get rid of the annual fee. You could even get a better interest rate, depending on the credit card issuer's offers and your scores.