Live oak (Quercus virginiana) would be one of the best trees for these requirements, although some find the leaf drop (and eventually acorn drop) it goes through in late winter or early spring an annoyance. Sand live oak (Quercus geminata) and southern magnolia (Magnolia grandiflora) are also possibilities. Green buttonwood (Conocarpus erectus) and mahogany (Swietenia mahagoni) would also be possibilities but both of these are somewhat cold tender and can be expected to suffer some cold damage in some winters. If you are located on one of the barrier islands the threat of cold damage would be somewhat minimized.

Other smaller growing native trees that may be suitable for shading a small area like a patio would include Florida privet (Forestieria segregata, yaupon holly (Ilex vomitoria), stoppers (Eugenia species including red, white, Spanish and redberry stoppers), hopbush (Dodonaea viscosa) and marlberry (Ardisia escalloniodes).

You can search for additional trees and other kinds of plants by specific categories using the Florida-friendly Plant Database:

http://floridayards.org/fyplants/index.php