Be patient with them for another month or two. Their root systems might've survived and will grow back, or start sprouting again from branches in spring (you can do the thumbnail test to see if any branches are still alive).
If you want to plant something else I'd hesitate to recommend without knowing where or seeing the situation. But if looking for a slightly larger shrub/small tree you could look into smoke tree/bushes, redbuds, jane magnolias, crape myrtles, dogwoods, Carolina allspice, rhododendrons, or butterfly bushes off the top of my head.
All those are gonna be in the 10-20' height range. You could also explore edible landscaping like blueberries (which are smaller too) or figs (though figs are a b*stard with cold weather and require a sheltered spot or being wrapped up like babies). All those are deciduous except rhododendrons. If you want an evergreen for privacy you could plant any of the various holly trees/bushes, or juniper/cedar etc. Just don't plant privet for God's sake. LOL. And if you plant the abomination that is Leland cypress you'll have to deal with a disease that will kill it or major portions of it before it reaches legal drinking age.
Those are some ideas to get you looking and see what's available, grows well, and you like best for the spot.