Any character can worship a god, but only certain classes actually benefit from it in terms of game mechanics
Appendix B: Gods of the Multiverse (from the basic rules or PHB) describes that people may worship any god... or even multiple gods.
Many people in the worlds of D&D worship different gods at different times and circumstances. People in the Forgotten Realms, for example, might pray to Sune for luck in love, make an offering to Waukeen before heading to the market, and pray to appease Talos when a severe storm blows in—all in the same day.
...
And a few people dedicate themselves entirely to a single god, usually serving as a priest or champion of that god’s ideals.
Your DM determines which gods, if any, are worshiped in his or her campaign. From among the gods available, you can choose a single deity for your character to serve, worship, or pay lip service to. Or you can pick a few that your character prays to most often. ...
If you want to be a "servant of your god", that's perfectly fine. The Acolyte background models this quite well, without affecting which class you choose. So long as you aren't thinking of gaining magic through your worship, then any character you create can be a servant of one or more gods.
Receiving spells from your god is modelled by specific classes
However, when you start talking about spells, that's where the "class restrictions" come into things. Although your DM may be imposing different rules depending on their setting, generally speaking, if you want to get spells from a god, that means being a cleric:
Divine magic, as the name suggests, is the power of the gods, flowing from them into the world. Clerics are conduits for that power, manifesting it as miraculous effects. The gods don’t grant this power to everyone who seeks it, but only to those chosen to fulfill a high calling.
Paladins may also gain their powers from a god, although paladins in 5e aren't tied to gods as much as in previous editions:
Although many paladins are devoted to gods of good, a paladin’s power comes as much from a commitment to justice itself as it does from a god.
Warlocks aren't as clean cut; generally, warlocks make a deal, a pact, with an "otherworldly entity". Whilst your DM could decide that such a being is a god, generally the implication is that it's another sort of powerful being, such as a archdevil, an archfey, an angel, etc.
A warlock is defined by a pact with an otherworldly being. Sometimes the relationship between warlock and patron is like that of a cleric and a deity, though the beings that serve as patrons for warlocks are not gods.
Finally, I will also mention druids and rangers, who also gain magic from "divine" sources (the distinction between divine vs. arcane magic isn't really as much of a thing in 5e, but many D&D players use those terms), although they may also get their magic from "nature itself", so they don't strictly need a god like clerics do:
Druids revere nature above all, gaining their spells and other magical powers either from the force of nature itself or from a nature deity.
Thanks to their familiarity with the wilds, rangers acquire the ability to cast spells that harness nature’s power, much as a druid does.
In your case specifically, I'd recommend rogue with the Acolyte background
Based on the part of your question that says:
I want to make a rogue who worships the Crow Lord because crows pick up shiny stuff, and I feel like a thiefy-rogue would work and maybe that character could get advantage on stealth and sleight of hand checks because of that. I thought would fit nicely with that, but he just shot me down instantly.
If you picked the Acolyte background, as I mentioned above, this would give you that "servant of the gods" flavour but without clashing with your class choice of rogue, and if you let your DM know that you aren't expecting to get any divine magic out of this, it's just for flavour, hopefully he should be fine with that.
As a rogue, you get something called Expertise at 1st level. You are allowed to add your proficiency bonus twice instead of once to any two skills you are proficient in. If you make sure that you pick Stealth and Sleight of Hand as two of the skills you are proficient with (rogues are allowed to pick four from a subset of skills, as explained here; these four plus the two you get from the Acolyte background should see you with a total of 6 skill proficiencies at 1st level), then you can pick those two skills as your "Expertise" skills.
It's not quite advantage, but you will still be extra-good at Stealth and Sleight of Hand because of it, and you can still flavour it as "guidance from the Crow Lord", even though in terms of the game mechanics, it's just your rogue's base class feature and nothing to do with the gods at all (which should hopefully keep your DM happy).