title_body: Conlang where the initial consonants of words have meaning?
upvoted_answer: Many languages mark things like those you mention at the beginning of a word. Noun class in Swahili and the other Bantu languages comes to mind. It doesn't require all roots to begin with a vowel; the prefixes also include vowels (as in Kiswahili).
  
  Russian has prepositions (not prefixes) such as в, which are pronounced as part of the onset of the following word (and it does sometimes cause initial consonant clusters), in addition to case. There's no reason why a conlang couldn't have the same as a prefix for gender, case or tense.
  
  You might also want to look at the WALS chapters Prefixing vs. Suffixing in Inflectional Morphology, Position of Case Affixes, and Position of Tense-Aspect Affixes for lists of languages that have these features as prefixes.