Clark County, at the extreme southern tip of Nevada, apparently has a USDA Hardiness Zone rating of around 9b, It but in the moutains in the area it can get colder. It is a subtropical desert climate, typical of the Mojave Desert in which it lies. Since you are looking for something to go with pine trees, it sounds like you might be at one of the higher elevations of the area. However, we will search in our Native Plant Database for small trees or shrubs native to Nevada and then check with the USDA Plant Profile for each tree we find to see if it is native to Clark County.
First, the good news - we found an even dozen trees native to Clark County, some referred to as shrubs, most with lovely flowers and/or foliage. Now, the bad news - only two, Yucca schidigera (Mojave yucca) and Washingtonia filifera (California fan palm) are evergreen, and are really more in scale as shrubs. There are small evegreen junipers and pines native to the area, but they would basically be more of what you already have.
Small Trees Native to Clark County, NV:
Follow each plant link to our webpage on that plant to learns its growing conditions, including amount of sunlight, soil type and moisture. At the bottom of that page you can follow a link to Google to get even more information.