First, get the day walk Tasmania book by John Chapman. Plenty of great ideas there. Second, if you're doing a round trip of the island, try to think of ticking off the most types of walks. So a mix of beach, cliff, mountain, plateau and waterfall walks. To follow my collegues' choices, I think that on the Tasman Peninsula Cape Raoul or Hauy is a brilliant choice. The rest of the peninsula has some good lookouts accessible by car. You'll notice that on the East coast, most of us won't say "Freycinet". Because although it's beautiful, it's quite touristy nowadays, and some other parts of the coast are even more enjoyable : Maria Island indeed, and Mt William NP (camp there if you can).
If it were spring or summer, I'd tell you to visit the Walls of Jerusalem, but with snow and 1000 m elevation gain to reach the various summits, it's a bit too much. Mt Murchison is indeed beautiful, again watch out for snow : it'd be dangerous, it's not a beginner's walk, although not that hard. In the North, you can enjoy Stanley and the Nut, beautiful area enven though not that wild, for the wild North, visit Narawntapu : the fauna is amazing. Rocky Cape NP is quite nice too, don't miss Anniversary Point. Don't forget the West coast, with Arthur River (the "end of the world" lookout is breathtaking) and all the coastal areas South from here, take the Western Explorer (if open) and camp at Trial Harbour if you can. I reckon Bruny Island would be good too for the end of winter, and Hartz NP has some nice short walks that could be suitable for winter.
For accommodation, don't forget
http://www.stayz.com.au , an Aussie equivalent of AirBnB, but with much more choice. Some brilliant houses for less than 100 $ a night there. I also can't emphasize enough how helpful has been the Hema "Tasmania Atlas & guide" that you can buy here :
http://www.exploroz.com/Shop/Hema+Tasma ... Guide.aspx . Plenty of hidden gems with all those waterfalls or lookouts, some great addresses and websites. And with the maps inside, you don't need anything else unless doing some serious walking.