1) It differs from city to city. Banks and some stores will be closed (mostly because it's Sunday), attractions are usually open.
People don't celebrate May 1st as they used to do. Most think of it as of beginning of spring and a day off, when you can meet your friends and go on a picnic. Demonstrations are possible, but few people take part in them.
2) Basil77 is right. SIMs are cheap, usually 2-5 dollars, depending on rates and mobile provider. You can ask a sellperson for advice (what SIM you should buy depending on your goals - calls abroad, local calls, etc.), because conditions are very different. They also can help you to add money to your mobile account - for free or for a few grivnas. I've never was asked for any ID when I bought SIMs, but maybe something changed lately (I doubt, though).
3) CoffeeCup's link is great. If you need a paper copy, you can buy a booklet with detailed map of Odessa near the train station. Such maps usually have public transport routes. It's very useful.