As you point out, paid fees result from two phenomena:
- Full nodes on the network enforce a minimum feerate for relay, which in recent history has been 1 satoshi per byte.
- Miners sort unconfirmed transactions by fee per byte, and include the highest ones first in blocks (whose size is limited to 1000000), as this maximizes their income. This results in a fee market where transactions pay according to supply and demand for space in blocks.
This means that while 1 sat/byte is the minimum to be relayed, it's not enough to actually get into a block, and as a result this minimum has become mostly irrelevant.
SegWit did not change these processes. There is still a minimum feerate of 1 satoshi per byte, and there is still a fee market.
What did change is the definition of size of a transaction. In SegWit, a significant portion of the transaction data is moved to the "witness", whose size only counts at a rate of 0.25. So for example a 200-byte non-SegWit transaction would be counted for the full 200 bytes, and 5000 of them would fit in a 1M block. If this were an equivalent SegWit transaction, maybe 120 out of those 200 bytes would be in the witness, resulting in an effective size of 80 + 120*0.25 = 110. Now 9090 such transactions fit in a block. The result of this new rule is that the optimal selection policy for miners also means looking at fee per byte, where bytes refer to this modified definition that discounts witnesses.
TL;DR: SegWit makes transactions cheaper by discounting portions of the data.