"I want a different bag."
違う is a verb so it connects to a noun with nothing but in its plain ending forms.
な is a connecting form of だ. It goes with the な-adjectives. Test if it should be な if you can and must end a phrase with だ/です。
きれいだ / きれいです OK >>>きれい な カバン
高いだ XXX / 高いです Optional >>> 高い カバン
持っているだ XXX /持っているです XXX >>> 持っている カバン
欲しい（ほしい） is an adjective literally meaning something like "wanted/desired".
If you literally translate わたしはちがうカバンがほしいです, it means something like "As for me, the bag is wanted/desired." The は marks the topic (usually the person who wants something), and が marks the thing they want.
Right... And the reverse is true as well, as far as I understand.
Probably we can think of verbs as if they were -u adjectives... Or adjectives as if they were -i verbs... At least, I think it helps me to think in these terms. I do not know how far we can go with this analogy but:
kawaii kaban -> a beautiful bag (a cat that is beautiful?) kaban wa kawaii -> the bag is beautiful.
chigau kaban -> a different bag (a bag that differs)
kaban wa, chigau -> the bag is different (differs).