On what was largely a good day for the seeds at Flushing Meadows, Ivanovic and Stosur were the biggest second-round casualties.
Both came into the final grand slam of the year in decent form, but that mattered little on a warm New York day.
Serbian eighth seed Ivanovic was convincingly beaten by Czech Karolina Pliskova, who ran away a 7-5 6-4 winner.
Pliskova faces 29th seed Casey Dellacqua next after the Australian left-hander's 4-6 6-4 6-2 win over China's Wang Qiang.
Stosur, the Australian 24th seed and 2011 champion, squandered match points in a 3-6 6-3 7-6 (10-8) loss to hard-hitting Estonian Kaia Kanepi.
After wasting a pair of match points in the third-set tie-break, Stosur was made to pay.
Kanepi has another seed in the third round in Spain's Carla Suarez Navarro, who disposed of American Coco Vandeweghe 6-3 6-3.
The winner of the Kanepi-Suarez Navarro clash could meet Williams, who thrashed American Vania King 6-1 6-0.
Varvara Lepchenko set up a clash against Williams with a 6-4 6-0 win over German Mona Barthel.
Kvitova, the Czech third seed and Wimbledon champion, also cruised through, beating countrywoman Petra Cetkovska 6-4 6-2.
Surprisingly, Kvitova faces Aleksandra Krunic next after the Serbian upset American 27th seed Madison Keys 7-6 (7-4) 2-6 7-5.
Belarusian 16th seed Victoria Azarenka, a two-time grand slam winner, eased past American Christina McHale 6-3 6-2.
Azarenka will meet Elena Vesnina after the Russian fought her way past New Zealand's Marina Erakovic 7-5 2-6 6-4.
Canadian seventh seed Eugenie Bouchard overcame Romanian Sorana Cirstea 6-2 6-7 (4-7) 6-4 in an entertaining contest.
Barbora Zahlavova Strycova will face Bouchard after the Czech 30th seed beat Romania's Monica Niculescu 4-6 6-4 6-2.
Russian 23rd seed Anastasia Pavlyuchenkova departed after a 6-4 6-7 (6-8) 6-3 loss to American Nicole Gibbs.
Gibbs will need to eliminate another seed to progress any further as Flavia Pennetta awaits after the Italian's 6-4 6-3 victory over America's Shelby Rogers.
The tournament of 15-year-old American CiCi Bellis came to an end as Kazakh Zarina Diyas eliminated the teenager with a 6-3 0-6 6-2 win.
Next up for Diyas is Russian 17th seed Ekaterina Makarova, who thrashed Slovenian Polona Hercog 6-1 6-2.