Hi and welcome, Anna. We lived in Salt Lake for 21 years before migrating to Florida, and our kids and grandkids are still there so I still have gardens to play in there when I visit.
Three perennials you should start with as the backbone of your sunny perennial garden are daylilies, iris and roses. For shady areas, hostas are excellent. There is a forum for each of those types of plants here on garden.org . All do great in your area and are readily available in a vast array of colors, shapes and sizes.
Another good source of what is available would be your local nursery - not HD or Lowe's or Wal-Mart but a place that only sells plants will have knowledgeable people and good quality plants that fit your needs. Btw, October is a great month to plant some perennials, and often the nurseries have clearance sales at this time of year as well. Just be sure to mulch your newly planted treasures well to prevent freezing/thawing and keep them from drying out through the winter.
If your soil is mostly clay like mine was in Salt Lake, you should try to find a good source of compost and amend the beds where you're going to plant your perennials, too. The Salt Lake County landfill makes fantastic compost, and it's available for a small fee. They even load it for you. We filled up my daughter's garden with 25 pickup loads of compost before we planted a perennial garden there a few years ago. So maybe find out if your nearest landfill makes compost too?
