We've been evacuating New Orleans for the past several years for hurricanes and Mardi Gras week. Mardi Gras Day is typically late Feb to early March. The crowds are usually moderate and the lines are not bad at all. One exception was when it coincided with Presidents Day weekend. I'm not sure but I think Pres. Day is around the 16th of Feb this year. The first week of March should get you there before Spring Break for much of the country.
A lot of people from N.O. go to Disney for Mardi Gras week, as that replaces spring break for many schools here. The rest of the country is still in school that week so it's not very crowded. This year Mardi Gras is the 24th, and we'll be there all week again! So I think either last week of Feb or first week of March should get you there between Presidents Day and Spring Break.