Which place or country is the first to start the new day?

I've just checked, and it looks like the Eastern tip of Russia opposite Alaska is the first place to cross the dateline. It's the most Eastern point on the Asian continent, and the dateline bends east to accomodate it. The place is called Uelen, and the point of land at the extreme is called Cape Dezhneva/East Cape.
(I did hear a Pacific Island taking credit once for the first to have new year, but I suspect it was PR rather than using a map reference).

satguru is correct that the Eastern tip of Russia is the point to the west of the dateline which is furthest east. But the island of Tonga in the South Pacific has a time zone which is one hour ahead of this (13 hours ahead of Universal time), so midnight at the start of the new day arrives in Tonga first.

https://www.timeanddate.com/time/zone/tonga

Tonga is right. They manipulated the time zone so they could be the first to greet the millenium.