Valery, is there a fence you could grow vines on? That would be the quickest way to create a privacy screen. Passionvines, Coral Honeysuckle, Pipe vines, Queens Wreath, Rangoon Creeper - all would screen beautifully and quickly. If the fence isn't tall enough, you could add lattice to the top for the vines to climb higher on.
Podocarpus are a beautiful, thick tree that grows fairly fast. Here's one with lovely blue-ish foliage
Podocarpus (Podocarpus elongatus Icee Blue®) They're sometimes used as hedges, but if you let them grow they make very nicely shaped trees. Another nice, large and very fast growing plant is Mexican Sunflower (Tithonia rotundifolia) which grows very tall and wide in one season, and will also give you beautiful yellow flowers in the spring and fall.
You could start with that, and then plant some of the native trees like live oak, or Southern Red Cedar which may take a few years to really screen your view, but will be beautiful and long-lived for the longer term. They'll also replace the habitat for your birds and native animals.
By all means, go to a good nursery and ask for native trees that grow quickly, see what they have. Big box stores don't get the good stuff, they just sell whatever the head office sees fit to send them, and often they're types that aren't well suited to where you live. Look up a nursery that lists "Native plants and trees" as a specialty and you will have a great selection.
I wouldn't mourn the loss of the big Ficus tree, either, as they are also a non-native and a very weak tree that blows over in high winds.
