But yes, as people figured out, orientation matters.
And if you roll the die into a crease, preferably one that's bent at exactly a 90o angle so the die can't rattle around -- or alternatively, use a gamebox lid that's been propped up -- then you don't have to do any pushing, measuring, or other extra work. The die just lands in one of 24 ways (12 edges x 2 orientations) and that's it.
The rest is a matter of arranging things so that you can read off an answer quickly -- preferably in a manner such that the less-math-inclined folks could be immediately convinced of the fairness of the process (*). So far, the best answer seems to be to use 4 colors to paint each pair of opposite corners of the cube -- or at least to imagine things this way if the frogs won't let you paint anything. Then you just say "uppermost north corner wins" (i.e., if your crease is running north-south) to get your choice of 4.
And if you need a permutation of 4, then it's "north face, start at the top corner, go counterclockwise" and read off the colors. This works because the 24 rotations of the cube give you all possible permutations of the body-diagonal axes (the group-theory wonks would say, "the group of rotation symmetries of the cube is isomorphic to S4, the permutation group on 4 elements").
(*) I suppose what got me on to this was the is the whole question of what's the simplest device you can carry around with you that can easily accomplish the widest variety of everyday randomization tasks (**); call it the Economical D&D Problem (i.e., how to play with just one die because you're too lame to go out and buy a full set, and how to mark it and otherwise set things up so that using it isn't too painful).
I figure specially marked cubical die + box lid gives you d2,d3,d4,d6,d8,d12,d24 and permutations of 3 or 4, pretty much instantly.
The next step is to realize that dodecahedral (12-sided) or icosahedral (20-sided) dice are likely to be better for this sort of thing if you think factors of 5 are likely to come up.
The rotation-symmetry group of the dodecahedron has 60 elements (30 edges to land on, 2 orientations for each; or 12 faces times 5 rotations each; or 20 vertices times 3 rotations each), and hence if it's marked in the right way, you can do all of d2,d3,d4,d5,d6,d10,d12,d15,d20,d30, and d60. It also happens that this group is isomorphic to A5, the group of even permutations on 5 elements (i.e., ones you can do with an even number of swaps), you can't get to the odd permutations unless you're willing to do an extra coin toss -- either that or we need to contrive a way to throw the dodecahedron through 4-dimensional space so that a "roll" can do parity inversions as well,... but let's not go there.
The icosahedron is essentially the same in that you have the same symmetry group as the dodecahedron -- where you were swapping faces before, now you're swapping vertices, and vice versa... so exactly the same set of rotations work for each. Though there are other issues; icosahedron has more places to put potentially useful labels (if one decrees that each face can only have one) and, finally, it rolls differently.
At this point I get to flame the D&D folks for not considering more carefully the markings for their 12&20-sided dice before launching the mass-production machinery. The result is that there are lots of stupidly (or at least, non-optimally) marked dice out there.
(On the other hand, I suppose it's a plus that these things are so ubiquitous that I don't have to explain "12-sided" and "20-sided" dice to people).
Really, for numbering an icosahedron, you want something like this (caution: half-assed stereographic projection follows):
The cool thing here is if some random process designates a face and a vertex, then you can read counterclockwise around the vertex starting from the face to get an even 5-permutation (which you can then reduce to anything else you want in the d2,d3,d4,d5,etc. list). I'll grant I'm still waffling on the most useful vertex coloring.
(... and wow do we need to get SVG adoped everywhere or something so I don't have to do these crappy conversions to .png anymore)
Various flies in the ointment for the icosahedron/dodecahedron
- you don't get d8 or d24
- you only get even permutations (i.e., you need that extra coin toss if you want all of them. buh).
- a 90o crease doesn't work anymore since you need something that's an angle between a pair of faces of the object
The most extreme case is the icosahedron being tossed into a 41.8o crease; it makes a nice, satisfying "THOCK". No long wait for it to stop rolling or anything. 41.8o being arccos(sqrt(5)/3) is fairly easy to construct, too, but you actually don't need to bother since any smaller angle works just as well -- instead of resting on two faces, the die hangs by a pair of parallel opposing edges that are fairly long with respect to the diameter (or at least longer than the corresponding edges for the dodecahedron), making things nice and stable. So all you really have to do is eyeball some angle roughly 40o or smaller and you're done. So even though you can't use the readily available boxlids anymore, it's all still quite doable.
(**) and no, I have no idea what might have gotten me onto the question of how to randomly order nominees making speeches for a given office. Yeah I know, in real life, everybody just draws straws, but ugh.
Deck of cards works, too, I suppose. Though you may have to convince people it's not stacked...