Todd laminating four sheets of foam the way you mentioned sounds like a good idea, and making a frame of 1 inch pvc would probably be sufficient. It would look more natural if you rounded the corners and made the shape irregular.
Those premade International floating islands are made from some type of recycled plastic fiber matrix which allows more surface area for biofilm to grow on.
The deer netting would increase surface area but possibly trap larger fish in the netting.
If you drilled lots of small holes in the foam it would allow water up to the soil and roots down below the island giving you more surface area. If you could find artificial garland that could be attached to the bottom or even lengths of rope as John Monroe mentioned, this would give you more structure for the fish.
