You're right, Tuesday is Two's Day.
Monday is actually a mispronunciation of the original name, One Day (pronunciations change over time).
Thursday sounds a lot like Four's Day, doesn't it? That's because it is Four's Day!
Friday was of course Five Day, and again the pronunciation has changed over time. But they both start with 'F,' so that's how you know it's true.
You may be thinking, "we skipped Wednesday?"
Yes, Wednesday is spelled weird. People say Wind's Day, it it's spelled Wed'n's Day, which was a Day for Weddings. It was originally Three's Day, but Three is a lucky number so everyone wanted to get married on Three's Day for good luck, so they renamed it Wedding's Day, which was shortened over time to Wed'n's Day.
.Of course Saturday was the day you get to relax and sit down after working all week, so it was named the day when everyone Sat'er Down to rest, so Sat'er Day.
But now we get to the part where you made the understandable mistake. Yes, One Day (Monday) is Day One, but that doesn't mean it's the first day of the week.
Zero comes before One! And Sunday is Day Zero. Notice it's actually named after the Sun, and what shape is the Sun? It's round, like the numeral Zero (0)!
So when they saw the big Zero of the Sun rising up it was like the clock resetting to Day 0, which makes Sunday the first day of the week.
Seems pretty obvious now that you've had it all explained to you, right?