Q: My wife and I found some empty shells of what we thought was some sort of beetle. Our first thought was that they were pine beetles from hell.
We looked on the Web and now believe them to be cicadas.
A: You are exactly correct: you found the discarded skins of cicadas.
The cicada nymphs emerge from the ground in summer and crawl until they find a tree trunk to climb. The then split their skin and emerge as a cicada adult.
Despite your misgivings, they do not harm trees or people but birds eat them readily.
You can see the whole process here: Cicada Emerging.
You can also identify cicadas by their songs. Go to Songs of Insects