A 1.5a reg is more than enough for the deck, the lm2576 ought to easily cope with 500ma, however I'd prefer a linear reg like you mentioned earlier and a bigger heatsink, up to you.
A diode drop is under a volt, you can compensate by adjusting the reg, a 7805 5 volt reg would probably work fine, you'd get 4.2 - 4.4v, the deck ought to be fine with that, it will be able to run the batteries down to lower than 4.5 anyway.
Just dont put a diode in the ground, put it in the + supply.