Dishwasher plug blocking disposal outlet
Re-wire the outlet so the top one is on the switch instead of the bottom one. Is this even possible, and if so, considering I've never done it before and it's under the kitchen sink without much room, how hard would this be?

This should be very straightforward. There are actually two different configurations possible. Find the one or two breakers and turn them off. The catch is that it could be one (hot split, 1/2 to switch and top receptacle, 1/2 to bottom receptacle) or it could be two (most likely as an MWBC, one hot to each 1/2). We can't guess which one it is. If there are two breakers then they should be a pair (technically, common shut-off, in reality almost always an actual &quot;double breaker&quot;).
After turning off the breaker(s), use a non-contact tester to make sure there is no power. Just in case. Then take off the cover plate and remove the receptacle from the wall but don't remove any wires yet. You should see two colored hot wires on the brass screws (or backstabs near the brass screws) and one or two white neutral wires on the silver screws.
If you have only one breaker involved then you should only have one neutral wire. If you have two breakers then you may have one neutral (MWBC) or two neutrals (two independent circuits - unlikely).
The actual work:

Swap the two hot wires. If they are in backstab connections, move to the brass screws (and flip top vs. bottom). If they are on the brass screws, just flip top vs. bottom.
If there are two neutral wires, swap them as well.

Put it all back together, turn on power and you should find the switch now operates the bottom receptacle instead of the top receptacle.

Put the dishwasher in the switch outlet, and tape the switch permanently on. Put a smart plug between the disposal plug and the wall, so I can control the disposal with my cell phone.

DO NOT DO THIS! EVER!
This is not only not &quot;normal&quot;, it is exceedingly dangerous. The reason the disposal switch is normally above the sink is so that you can see exactly what is going on when you turn on the disposal and so that you can immediately turn it off if there is a problem. If you control by phone, numerous scenarios could happen, including &quot;someone else borrows your phone to make a call and accidentally starts the App while you are working in the sink&quot; and &quot;phone crashes right after you turned on the disposal or the phone rings while the disposal is on, will the App stay focused?&quot; etc. DO NOT DO THIS! EVER!

Put the dishwasher on an extension cord. I've read this is a really bad idea, but are there particular extension cords that would make this safe?

This is OK as a temporary solution, until you rewire the receptacles.

Cut the cord and put a new end on it. I've never done this, so is this difficult or dangerous?

Not cut the cord, REPLACE the cord. This actually is not too hard on a properly designed appliance. But the work involved is comparable to &quot;swap wires in the receptacles&quot; and doing that doesn't actually cost you anything, where this will cost you a new cord.