Devon is right along my commute so I typically go there. The nice thing is that they actually measure the tread depth and only rotate if necessary. When I first got the car I checked with Costco to see if they would do it, as I like their tire center. Unfortunately they will only do it if you purchase the tires there.
Any reputable shop should be able to rotate the tires without an issue. There is nothing special about rotating tires on a Tesla, although as with any car they should be careful lifting the car and removing/tighting the lugnuts.