Natural setting for characteristic classes? In my mind, algebraic topology is comprised of two components:


*
*Chain complex information, which is intrinsic information concerning how your object may be built up out of simple "lego blocks".

*Characteristic classes (bundle information) which give information on how your object might stably embed in some sufficiently big standard object.

Chain complexes make sense over any abelian category.
I have no corresponding intuitive understanding of what the "natural setting" for characteristic classes should be. The classical theory looks to me like a concession to the sad fact that, at its very basis, manifolds are locally modeled on Euclidean space and are not intrinsically defined objects. This is reflected in the central role played by specific concrete spaces such as the Thom spaces MSO(n), the real and complex Grassmanians used to define Wu classes, and the classifying spaces BU and BO concerning which we have Bott periodicity.
I realize that I have no understanding of any of this. Part of this feeling is because I really don't understand what forces us to consider these specific concrete spaces, to the exclusion of all others. If constants appearing in physics ought to be conceptually explained, I'd like to understand these "constants" in mathematics. Can one work with characteristic classes in a more general setting, to parallel abelian categories? What about over number fields, over arbitrary rings, or in finite characteristic? Can I replace Lie groups such as SO(n), U(n), and O(n) by groups of Lie type for instance, and still have a "useful" theory?
My question is then:
What is the most general categorical setting for a "useful" theory of characteristic classes? In particular, are all of those special concrete spaces really necessary, and if so, why?
 A: Here is a perspective that might help to put characteristic classes into a more general framework.  I like to think that there are two levels of the theory.  One is geometric and the other is about extracting information about the geometry through algebraic invariants.
Bear with me if this sounds to elementary and obvious at first.


*

*The geometric side:  We have some class of bundle type objects which admit a theory of classifying spaces.  This allows us to swap bundles over $X$ for maps of $X$ into some fixed space, which I will call $B$ for the moment.  Equivalent bundles over $X$ give equivalent maps to $B$.

*The algebraic side:  We study maps from $X$ to $B$ by looking at their effect on some type of cohomology theory. The point is that we push the problem of studying maps $X \to B$ forward into an algebraic category where we have a better hope of extracting information.  
The passage from geometric to algebraic certainly throws some information away; this is the price for moving to a more computable setting.  But in the right circumstances the information you want might still be available.  
Now, a general framework for this might be the following.  Bundles in the abstract are objects that are local over the base and can be glued together.   This is precisely what stacks are meant to describe.  So think of bundles simply as objects that are classified by maps of $X$ to some stack.  This can make sense in any category where you have a notion of coverings (a Grothendieck topology), so we don't have to stick with just ordinary topological spaces here.  If you know how to talk about coverings of chain complexes then you can probably make a chain level version.  But more concretely, we could also be talking about principal $G$-bundles for just about any sort of a group $G$.  Or we could talk about fibre bundles with fibre of some particular type (in my own work, surface bundles come up quite a lot).
As an aside, if you happen to be working with spaces and you want to get back to the usual setting of classifying spaces like grassmannians and $BO$ or $BU$ then there is a way to get there from a classifying stack.  Take its homotopy type; i.e, if $B$ is a stack, then choose a space $U$ and a covering $U \to B$, then form the iterated pullbacks $U\times_B \cdots \times_B U$ which give a simplicial space - the realization of this simplicial space will be the homotopy-theoretic classifying space).
Now, we have some class of bundle objects classified by a stack $B$.  To have a "useful" theory of characteristic classes we need a cohomology theory in this category for which


*

*We can compute enough of the cohomology of $B$ and the map induced by $X \to B$.

*Enough information is retained at the level of cohomology to tell us things we want to know about morphisms $X \to B$.


It is very much an art to make a choice of cohomology theory that helps with the problem at hand.  
I just want to point out that if you are working with vector bundles, then you needn't think of characteristic classes only as living in singular cohomology classes.  A vector bundle represents a K-theory class, and you can think of that class as the K-theory characteristic class of the bundle.
Addendum:  Just to say something about why we work with things like $BO$ instead of $BO(n)$, let me point out that it is a matter of putting things into the same place so we can compare them.  Real rank n vector bundles have classifying maps $BO(n)$, and if you want to compare a map to $BO(n)$ with a map to $BO(m)$ then a natural thing to do is map them both to $BO(n+m)$.  And then, why not go all the way to $BO(\infty)=BO$?  It's just a matter of not having to compare apples and oranges. 
A: I hope that "A note on characteristic classes: Euler, Stiefel-Whitney, Chern and Pontrjagin" is a useful addition to the discussion.
A: [I tried to make this a comment, but ran out of space...]
I'm not 100% clear on your question, but do see some possible answer(s). 
The homotopical generalization of a manifold is a Poincare duality space.  Instead of tangent bundles those spaces have "Spivak normal fibrations."  This fibration itself or corresponding lifts of the classifying map for this fibration to other structure groups gives rise to characteristic classes for the manifold akin to the stable embedding description you gave.  
To elaborate on this structure group idea, a fiber bundle (for simplicity) F -> E -> X can in many cases be classified by a map from X to the classifying space BAut(F), of the space of automorphisms of F (could be homeomorphisms but could also be linear maps if F is a vector space, holomorphic maps if F is complex, symplectic homeos... you get the picture).  If G -> Aut(F) is any homomorphism (usually an injection), one can ask if the classifying map X -> BAut(F) lifts to a map from X -> BG.  Informally, this lift exists if "G has enough data to make this bundle."  (For example, if G is the trivial group, then one is asking if the bundle is trivial.)  If it does, then the cohomology of G would give rise to a collection of characteristic classes for X.  Here G can not only be other groups of Lie type but in principle could be any kind of group.  The rub is finding something "useful" as you allude.  Sure, the Monster could be a structure group for the  tangent bundle of my manifold.  But outside of the classical linear groups and maybe some cases in which say G is elementary abelian, both concrete applications and general theory are hard to come by.
In the end, I don't think there is a clean answer for what is the right categorical setting, as abelian categories are to chain complexes.  For basic characteristic classes you just need (functorial) classifying spaces and (generalized) cohomology.  There are certainly settings other than the usual category of topological spaces where those exist and I could imagine some sensible axioms one could develop.  But again one would be pretty far from having say all of the structure of Chern classes at hand.  For characteristic classes of manifolds, you would need generalizations of the notion of Poincare duality space with its Spivak normal fibration.  I don't know of any other categories where those exist (though I wouldn't be surprised if there were).
A: decided to leave this as an answer instead of a comment:
May wrote a book called classifying spaces and fibrations where he constructs such classifying spaces (you can get a copy of it for free on his website). In it, he makes a lot of use of the two-sided bar construction which is very general (works for any monoid and two spaces on which the monoid acts).
It seems like the natural setting for characteristic classes is really something like bundles or fibrations. PS the use of MSO and various grassmanians has more to do with classifying bundles than manifolds being locally euclidean, these spaces still tell you all about bundles over CW complexes or cobordism over CW complexes. 
I get the impression that, as mentioned above, you look at induced maps in cohomology coming from the classifying maps of variously structured bundles or fibrations, once we have our classifying spaces we can look at the cohomology of them with respect to various different theories. so we get characteristic classes for every cohomology theory just as Jeff mentioned.
As far as relying on things that are locally euclidean, i think you have it a bit backwards. People care about manifolds first, we try to understand their geometry with vector bundles that live on them, to understand these we use an algebraic invariant. we can use any contravariant algebraic invariant to get some sort of characteristic class. This does not require any sort of locally euclidean condition.
I would love to understand the chern comment more.
ps sorry if overlaps too much with the above answers
