But what if the sandals were not waterproof?
On your modified data structure, the following should work:
SELECT `Shoe name`, `Waterproof`, `Left/Right`
FROM shoe_table
ORDER BY CONCAT( `Shoe name`, ', ', `Waterproof` ), `Left/Right`;
You can try:
select * from shoes order by 2, 1;
OR by column name:
select * from shoes order by Waterproof, `Shoe name`;