A solid core wire is just a wire made from a single strand of (usually) copper. Stranded wire is made from multiple smaller stands of wire.
Solid core is typically more stiff than stranded, but is easier to terminate and is generally a better conductor.
If you're doing in-wall or attic wiring, I'd suggest using solid cable. You don't need to worry about flexibility much (especially since Cat5/e conductors are typically around 20-28 AWG, which is pretty thin and flexible anyway). In many cases, the sheath of the cable has a greater impact on the flexibility than the type of wire used. If you are going in the attic or walls, I recommend getting plenum rated cable. It's certified to not give of toxic fumes when it burns (in case of a house fire).
Stranded or solid, it makes no difference, just rely on the "category" rating to get the cable performance you want. At this writing, I would suggest Cat 5e at the minimum, and if you are willing to spend a few more pennies per inch, Cat 6. Solid cables are typically used for building wiring, the long hauls, while the stranded ones, with their inherent flexibility, are used for patch cables.
If you are looking for a quality job, make sure your RJ45 ends are made for the correct type of cabling (solid or stranded). The RJ45 ends made for solid have 2 or 3 small blades that are meant to pierce the insulation and then "pinch" the solid conductor. The RJ45 ends made for stranded, have a small blade that no only pierces the insulation, but is made to bury itself in the midst of the stranded conductors. And yes, you do need very good eyesight to tell the difference. The folks at home improvement stores wil probably have no idea there is even a difference.
Regarding your choice of plenum (sometimes called fireproof) over non-plenum, use building code as your guide. Code calls for plenum any time the wire is part of your HVAC ducting. So if you are running your cables through your cold air return ducts, or if you're running it through a false ceiling that is part of the cold air return for your heating or AC system, you will need to use plenum. If it's just in your walls, or between your floor joists, or in your attic, as is the case with most new construction, use the plain-jane stuff. Most residential construction does not have drop ceilings nor does it route cabling through your cold air return ducts (for example ductwork for forced air heating or possibly central air conditioning).
Some organizations, notably public schools, use plenum for everything in order to avoid any confusion between the two types -- although strictly speaking they would be able to use non-plenum in many places.
As an observation, most electrical wiring has the PVC outer insulator, just like non-plenum networking wiring. You will note that in new construction it is everywhere; ceilings, attics, walls, between the floor joists, etc. Where you will not see this standard electrical wiring (at least without being encased in conduit) is... any location or space that is part of an air handling system. Sound familiar?