Measuring Easiness
I agree with Oliver that we measure language difficulty based on how hard it is to learn from a given native language. However, I still believe that we can come up with language features that make a language easy to learn in general. To measure this, you would want to take the number of hours it takes to achieve a certain level of proficiency in a target language from 50 source languages (the languages with the most speakers). After this come up with an average by weighting the numbers based on number of speakers. A language with an average of 456 hours would be easier to learn for the average person than a language with an average of 678 hours. This is of course not a method of deriving 'absolute' difficulty but it's good enough for what I want. Now, actually running this experiment would take a lot of time but for now it's good as a thought experiment to figure out what the goal is.
Phonology
Trying to get the sounds right in a new language can be very time consuming. To counteract this an easy language should use phonemes that are common amongst the world's most spoken languages. As Richard noted in the comments the language Toki Pona has a very simple phonology that would be perfect for this. Toki Pona has nine consonants p, t, k, s, m, n, l, j, w and five vowels a, e, i, o, u. Not only are these very common phonemes but there is also the added benefit that there are no voiced/voiceless pairs. The reason this is useful is because it helps people whose language contains only one of the voiced or voiceless forms of a consonant. As an example, Arabic has no 'p' sound and therefore when they see the world 'pala' in a theoretical easy language they might pronounce it as 'bala'. Since there is no 'b' sound people will recognize that they are saying 'pala'.
Vocabulary
Having a vocabulary that everyone would recognize would be useful but it's unfortunately not possible. The best attempts at creating such a vocabulary would only be useful for around 15 percent of the world's population. Add to this the fact that phonology is more important, and using the simplified phonology, you would not even be able to mimic a lot of the vocabulary from a natural language. However, there are still some things that would help make a language's vocabulary easier to learn: avoiding homonyms, making common words short, constructing words to be easy to pronounce (ex. avoiding complex consonant clusters).
Writing System
It has been proven that phonetic writing systems are easier to learn than logographic systems. Between phonetic writing systems (alphabet, abugida, abjad) it's less clear what the easier to learn system is. However, it doesn't really matter due to the overwhelming adoption of the Latin script world wide (70% of the world's population use it). Even in places where the native language does not use the Latin script people will still have significant exposure to it. Because of this an easy to learn language should use the Latin script. The words should also be completely phonetic in their spelling. This allows learners to read, pronounce, and spell any word without having to memorize a bunch of spelling rules and exceptions.
Regularity
This one is self explanatory. A language that has regular grammar and no exceptions to its grammar rules is easier to learn. This should apply to all forms of grammar (inflections, word order, usages). As an example, if English were to always use -ed to make verbs past tense it would be easier to learn (swimmed, eated, falled).
Lack of Unnecessary Features
Just as biological evolution has left human bodies with a large amount of inefficiencies, language evolution has left natural languages with a large amount of inefficiencies. It would take a long time to go through these as there are many, so I'll just use the gender example from the question. As jknappen said in the comments grammatical genders do have a small amount of communicative power in that they can, on occasion, avoid ambiguity of two things. However, this only happens when there are two things potentially being referred to, when it's not clear based on context which thing is being referred to, and when the two things are different genders. Example from Wikipedia: "a flowerbed in the garden which I maintain" vs "ein Blumenbeet im Garten, das ich pflege". This is very rare and not useful enough to merit spending a significant amount of time learning genders.