Are we trying to come up with terms for regular folks or computer folks? I think the scope of the problem should be defined before really entertaining potential solutions. If I look at this thread and pretend that we are trying to name a JPEG file, the suggestions sound to me like the following names for a JPEG: "Tri-chromatic quantized raster image". "Non-palletized discrete cosine color map". Meanwhile, the rest of the world has settled on calling these "photos", and calling them "JPEG's" where there is any need to make a distinction as to how the picture is encoded.
If I put myself into "regular folks" shoes, there should just be one thing: "bitcoin wallet". You double click it (just like your e-mail inbox) and there's your bitcoins. Anything more complicated than that screams "this is for computer experts only". The Apple computer company has risen to stardom due to their intuitive grasp of this concept, and Microsoft is getting the burial it deserves.
Whether it's deterministic or not shouldn't even be in the regular user's lexicon. Whether it's random or non-random or whatever, shouldn't be either. Keep in mind that for the vast majority of users, if you simply tell them that a "bitcoin wallet" has the property of being able to spew out as many receiving addresses as they'll ever need, then they will take that at face value, without needing some sort of adjective qualifying the wallet as having that property.
From a technical standpoint, what kind of wallet it is should be denoted by the file extension, and the differences between certain kinds of wallets should be assigned certain file extensions (the extensions themselves may or may not stand for anything).
This way, if they need to make a distinction, it might roll off the tongue the easiest by calling it a ".BW3 bitcoin wallet", automatically incorporating by reference the exact nature of the "determinism" and "randomness" inherent in using the wallet, the same way calling a picture a JPEG automatically implies usage of the discrete cosine transform and Huffman encoding without the user having to say or even think about these.
I've been battling this question myself.
The important question to ask is "what do users interact with?" Literally, what do they see on the interface? They interact with "wallets", of various kinds. They interact with "transactions" and "labels", and "confirmations", and "transaction amounts". The names need to start simple, and have a hierarchy that accommodates the various gradations of user education.
You can't just call everything a "wallet" with no qualifiers, because that neglects the profound differences between different kinds of wallets. For users that use nothing more than "online, maybe-encrypted wallets", using "encrypted" or "unencrypted" is all the qualifier they need. But once you go beyond "standard" usermode, users have options and need to understand what those options are. And that's a million times easier if there's consistent names between the applications giving them these options. Armory uses deterministic wallets, Bitcoin-Qt uses "loose-key" wallets -- the user should care that "loose-key" wallets need to be backed up regularly. In this sense, anything that will show up on the user interface to the 80th-percentile-and-lower user base, should have simple, unique, fewer-syllables-preferred names.
Things that only matter to developers, can have as complicated a name as they wanted. "TxOut trees" are fine because developers aren't actually developers if they're not used to things like that. And "deterministic wallets" are fine for developers. But for users, especially ESL and not-so-smart users, we need at least something they can call it, even if they don't understand it.