Is my AC right-sized for my house
The lack of insulation on the ducts in the floor is of no concern as the floor is in the conditioned space (ie, the area around the ducts is supposed to be cooled.) If the ducts were in the attic that would be a BIG deal.

The very low insulation in the attic seems like both a contributing problem, and the most easily solved one. Either rent a blower and buy some insulation or hire a company to do the whole job and insulate the attic a lot better. Read up carefully before deciding to try the "free blower with 10 bags" at the big box stores. 12-16" is a good number to shoot for, where possible, but you may (probably will) need to baffle for your roof vents at the edges to go that high.

Better windows will HELP but they are more costly and complex to do and involve a smaller area (thus, less overall contribution to the problem) than the attic does - grab the low-hanging fruit first.

Improving attic ventilation along with or before the added insulation will help with both cooling and with ice dams by keeping the attic space above the insulation closer to outside air temperature.

If you find that your system is still undersized, adding a couple of higher SEER mini-split heat/cool systems (on the upper floor, perhaps one at each end of the hallway) might be a better approach than replacing the whole thing. Might not, as well, but should at least be considered, IMHO.