I have been on a few cruises.. and I have seen many military members wear a uniform to the formal dinner.. However, they were in mess kit, and not in DEU with a bow tie..
Most men will be wearing a tux, I think you would be pretty under dressed in DEU.. Mess kit on the other hand, looks quite sharp.
Cheers,