When I create a new managed package (effectively an upgrade of my first application), will I need to pay the fee again to have it security reviewed?

No. If you develop a new version in an already approved package, once you click "Start Review" for the new version, it’ll be automatically approved and you can associate the new version to your listing.