In fact the first way, creating a temporary, is more readable for two reasons:
1) it's more concise
There's less code to read, there's no unnecessary local variable introduced, and no potential name clash with another local, or shadowing of any variable with the same name in an enclosing scope
2) it communicates something that the second form doesn't, that the object is being used temporarily.
Reading it, I know that that instance is never going to be used again, so in my "mental compiler" that I use to understand the code I'm reading, I don't have to keep a reference to it any more than the code keeps a reference to it.
As Mehrdad notes, though, doing it with a Random class isn't a good idea.
As he also notes, the redundant parentheses make it less concise; unless you're in a dusty corner of a language, assume that competent programmers know the language's operator precedence. In this case, even if I don't know the operator precedence, the alternative parse (calling new on a function's return) is nonsensical, so the "obvious" reading is the correct reading.
int RandomIndex = (new Random()).Next(0,100);
int RandomIndex = new Random().Next(0,100);