I am not a Ukrainian resident as you know but I can answer two questions.
1) Yes 1st May is celebrated and I guess many shops can be closed (exept groceries of cause). About celebrations I dunno, I guess it's some labor union marches in big cities like in Russia.
2) You can buy Ukrainian pre-paid sim card everywhere in Ukraine, it's pretty easy and cheap. You only need to show ID (I guess your passport would be enough). Little shops that sells mobile phones and sim cards are everywhere, you just can't miss them, especially in such a big city like Odessa. Also Ukraine had one of the cheapest prices for cell-phone calls in Europe, at least it's much cheaper than in Russia and our prices also quite affordable.