To get the first Tuesday of the month, use WEEKDAY() to find the day of the week for the first of the month.
If the month starts on a Sunday, add 2 days. If the month starts on a Monday, add 1 day. If the month starts on a Tuesday, add zero days. If the month starts on a Wednesday, add 6 days, and so on.
I prefer this method to the next method because I find it easier to read. I also add 0 days versus not adding any days because it keeps the parallel structure of the formula, and makes the formula easier to adjust if you want a different day of the week.
Because the formula for the {First of Previous Month} is used so many times in this formula, I prefer to keep it in its own formula field instead of trying to combine both formula fields into one.