I was offered a position at another company and have limited time to give my two week notice for my current job. However, I see that if I give my notice today (Monday 5/16) then exactly two weeks from now would be Memorial Day (Monday 5/30). Should I just go ahead with notice considering that as my last day? Or should I just make Tuesday 5/31, which is the day after the holiday, as my last day? I also thought of making Friday 5/27 my last day, but I'm not sure if that would be considered full two weeks notice.
Most companies would probably prefer not to pay you for the holiday. I did this once and gave notice as of the day I wanted as my last day in my resignation letter. It even happened as the second day of a two-day holiday at Thanksgiving. I then told them that I realized this was a holiday and that if they wanted to make the last work day as the last day of my notice that was OK with me. I was lucky enough to be paid, but there is good chance they will be happy to let you leave on Friday and not pay for the holiday.
I would not offer to stay until the 31st in your case. If they insist I would agree (unless that was a showstopper for the other job), but let them suggest it. As I said, more likely they will prefer not a to pay a holiday for someone who is not going to be there.
It's two weeks' notice, not 10 working days' notice, and on top of that it's a courtesy, not a requirement. You ought to provide your company with as much time as you feel is appropriate for them to find a replacement. I've worked at places where the winding down period was spelled out in months, not weeks, and other places where I came into work and people were like "okay, we have no need for you anymore, bye".
If you don't want to burn bridges, of course, don't just walk up to the boss and say "I quit". However, I would go so far as to say that a company that was like "NO YOU CANNOT QUIT UNTIL THE FOLLOWING TUESDAY BECAUSE TWO WEEKS DO NOT INCLUDE HOLIDAYS HERE" is probably not a place you want to ever return to work at anyway.
You're worrying about this way too much.
If you need to start at your new job on Tuesday 5/31 then simply say so. If you boss has an issue with it he will tell you about it and you can come to an arrangement.