A computing device may include a memory and a processor cooperating with the memory and configured to access a plurality of connection lease templates corresponding to published resources stored in a shared memory. The processor may further be configured to provision connection leases for respective client devices using a connection lease issuing appliance based upon the stored connection lease templates. The connection leases may be provisioned on demand responsive to selection of the published resources by the client devices, and the connection leases may provide instructions for connecting the client devices to virtual computing sessions corresponding to the published resources.