A computing device may include a memory and a processor cooperating with the memory and configured to generate connection leases for published resources selected by client devices. The connection leases may provide instructions for connecting the client devices to virtual computing sessions corresponding to the published resources. Each connection lease may include a published resource lease component unique to the selected published resource, and a common lease component shared by a plurality of different published resources.