- Pasta? Pasta is absolutely amazing. It is an extremely dense source of calories, which doesn't rot, is super-compact, and only requires water and heat to cook. Great for armies on the march.
- Coffee? Coffee's been around a long time, but high-pressure espresso is relatively new.
Other fairly basic staples are newer than you might think, like Potatoes (16th Cent.), Or Tomatoes (17th Cent.)
Edit: Also limes for sailors.