Why would CREATE INDEX with "online" mode suddenly slow my database down? Earlier I used CREATE INDEX ... WITH(ONLINE=ON) without any problems - the statement would run in parallel with user queries and not slow them down at any time. Then suddenly I see that once I start the statement the database slows down greatly - user queries pile up, usually with PAGEIOLATCH_SH wait mode and the database effectively becomes unusable until I cancel the statement. The slowdown begins immediately after I initiate the statement execution. It happens both when I try to create an index that differs from existing indices and when I try to create an index identical to one of existing indices (with a different name of course).

What could possibly cause such change?
The OIB is causing your DB to run over some SLO limit (most likely IO or Log IO), causing resource governor to kick in. See Azure SQL Database resource limits.