In C#, if the lifetime of your throwaway data structure is very short and tightly scoped (i.e. you only use it inside of one method), you could use an anonymous type. If it's not, I usually find that it's worth it to define a class. Since you're in prototype mode, don't get caught up early on in concerns about good object-oriented design - often I'll just plunk out a class with public fields for use as a data structure and move on.
Also, if immutability is the thing that's important to you, often in the prototype phase (especially when you're the only one working on the code) it's good enough to simply keep in mind that you shouldn't be mutating state. You can always come back later and define full constructors, put "readonly" on members, and upgrade fields to Properties and fix the rest of the code with refactoring tools or a quick find/replace.
public string Example { get; }
You can set it in the constructor and only the constructor.
On the other hand in C# it's still relatively hard/annoying to build Structural Equality into your classes (which anonymous types and tuples both handle for you) where the equality of two objects is based on the contents of their properties rather than the equivalence of their references. (Ease of Structural Equality is the number one reason for my typical reliance on Tuple as I tend to use tuples often as Dictionary<K, V>/ILookup<K, V> keys.)
Also, good call on structural equality, I hadn't even considered that and it's really valuable. One thing I've seen people do is create named tuples by inheriting from Tuple, which (I think) works but seems a little silly/ugly.
using MyTuple = Tuple<string, string, string>;
But that's of limited utility (you have to include it in every code file, for instance) and I don't recall the exact circumstances but I recall it being brittle the last time I used it heavily (it was something like the compiler would fail to compile things that should be fine due to it forgetting a type alias half-way through a file), but that was also several compiler versions ago.
I try not to leak Tuples between classes: it's easy enough in the API for your class to "unsplat" your tuple usage in any method calls other classes might need.
Also, Tuples are likely to become even easier to read/maintain in C#7 or so, as F#-like syntax for Tuples is a strongly favored proposal: https://github.com/dotnet/roslyn/issues/347