Bought a brand new SSD Samsung 850 evo, plugged in, restart macbook, hold option, and no disk utility screen

Solution 1:

Try using a different thumb drive, because it sounds like yours is broken. Do the same thing and let me know how it goes.