The Magellan dining room is on deck three...the other two (DeGama on deck 4 and Columbus on deck 5) are balcony area dining rooms that look down onto the Magellen area. All three decks have tables that are near windows. If you don't like your table you can always check with the Maitre d' to see about changing your seats.
Explorer - X 4
Deck three was hard to get to and hard to rush out to the show following diner. I would take deck 5 if given the choice over 4. Again, as the other poster said its really one dining room with the upper 2 floors around the sides. Deck 4 on the ship to go from the dining room to the main show you have to pass thru the casino and they designed the casino without a straight path thru it!!! really hard to walk around the people, machines, drink servers,and don't forget a few steps up and down, etc... Did it on purpose to get you to stop and play??