I'm currently just beginning to learn Russian so I'm trying to memorize the top 500 nouns... and then I'll do that same for adjectives and verbs, and everything else (obviously not just that but yeah). Should I be learning the gender too or is that not too important...?
Very advisable in my opinion as a native speaker. And it's not very difficult, because gender in Russian is signified with the ending.
This should simplify their inflexion for you, since there're differences in inflexion of words of different genders.
And also will give you an idea of correct agreement of adjectives and verbs because they all have a gender aspect which depends on the gender of the noun.
If you don't do it right away, sooner or later it will catch up with you and you'll still have to learn the genders. Of course not everything may sink in at first, but what does may facilitate the ability to figure out gender of previously unfamiliar nouns further down the line.