Here are some partial answers:
1- Usually the fusion category is the category of bifinite correspondences, i.e. Hilbert spaces with actions of $N$ and $M$ whose module dimensions are finite. Jones has a result saying that a bifinite correspondence is irreducible if and only if the algebraic module of bounded vectors is irreducible (on his website, two subfactors and the algebraic decomposition...). This means the fusion category of bifinite correspondences should be equivalent to the fusion category of algebraic bimodules (you probably need bifinite in the sense of Lueck, but this is very technical). The former category is generated by the $N-M$ correspondence $L^(M)$, and the later category is generated by $M$ as an $N-M$ bimodule (generated in the sense of taking tensor products and decomposing into irreducibles). In fact, Morrison, Peters, and Snyder use the algebraic category in their recent paper on extended Haagerup (arXiv:0909.4099v1).
2- This isn't what you're asking, but $L^2(M)$ as an $N-M$ bimodule is a Morita equivalence from $N$-Hilbert modules to $M_1$-Hilbert modules where $M_1$ is the basic construction of $N\subset M$. I just think it's an interesting point to bring up.
4- One of the best ways of constructing subfactors is via planar algebras. Given a suitable fusion category, one can construct a planar algebra. Typical examples of these nice fusion categories are the fusion categories arising from the representation theory of a finite group or a quantum group. This gives rise to a family of subfactors. In fact, since (for finite groups) there are only finitely many irreducible representations, we have that this planar algebra will be finite depth (see arXiv:0808.0764, section 4.1), and the subfactor constructed from this planar algebra will be finite depth as well. When someone says "exotic subfactor," they mean a finite index, finite depth subfactor that doesn't appear in the well known families coming from these fusion categories. To date, the best way of constructing these subfactors is to stumble upon a finite bipartite graph which doesn't appear as a fusion graph determine if it can be a principal graph for a subfactor. This has inspired a program to classify all principal graphs which can occur (see the extended Haagerup paper for a synopsis of this as well).
Tie in to 3- Two exotic subfactors, namely the Haagerup and extended Haagerup subfactor, have been constructed by finiding a subfactor planar algebra with the appropriate principal graph inside the graph planar algebra of the bipartite graph (this technique was first explored in detail in Peters' thesis). These subfactors have index equal to the square of the norm of the graph, which is the Perron-Frobenius eigenvalue. In fact, if a finite index subfactor is extremal (irreducible implies extremal), then the norm squared of the principal graph is always the Jones index. (One typically computes Jones index by computing the von Neumann dimension of the $N$-Hilbert module $L^2(M)$.)
5- I know that Kawahigashi et al. (see arXiv:0811.4128) have found a net of type $III_1$-factors corresponding to intervals on the circle. I would recommend starting there.
Here is one set of data that will be sufficient. To get the monoidal structure you don't actually need a (monoidal) functor $C \to C \boxtimes C$. It is sufficient to have a bimodule category M from C to $C \boxtimes C$. You will also need a counit $C \to Vect$, and these will need to give C the structure of a (weak) comonoid in the 3-category of tensor categories, bimodule categories, intertwining functors, and natural transformations.
To compute what the induced tensor product does to two given module categories you will have to "compose" the naive tensor product with this bimodule category. This can be computed by an appropriate (homotopy) colimit of categories. It is basically a larger version of a coequalizer diagram. This is right at the category number where you will start to see interesting phenomena from the "homotopy" aspect of this colimit, which I think explains the funny behavior you're noticing with regards to bases.
Finally, you may get a braiding by having an appropriate isomorphism of bimodule categories,
$ M \circ \tau \Rightarrow M$
which satisfies the obvious braiding axioms. Here $\tau$ is the usual "flip" bimodule.
Best Answer
I find the area your question covers very interesting and am looking forward to seeing what answers people come up with. I thought I would supplement my rather minimal answer from a few days ago. I'm not really providing any work that links all these ideas together, rather I'm giving some useful references for your quest.
Peter Freyd and David Yetter (1989). "Braided Compact Closed Categories with Applications to Low-Dimensional Topology". Advances in Mathematics 77: 156–182.
A. Joyal and R. Street, The geometry of tensor calculus, Advances in Math. 88 (1991) 55-112
André Joyal and Ross Street. "The Geometry of Tensor calculus II". Synthese Lib 259: 29–68.
André Joyal, Ross Street, Dominic Verity (1996). "Traced monoidal categories". Mathematical Proceedings of the Cambridge Philosophical Society 3: 447–468.
In fact, many things by Ross Street
Functorial Knot Theory: Categories of Tangles, Coherence, Categorical Deformations, and Topological Invariants (Series on knots & everything) by David N. Yetter (Author)
Many works by Bob Coecke and Samson Abramsky (eg. Temperley-Lieb algebra: From knot theory to logic and computation via quantum mechanics) are certainly accessible.
The Catsters youtube channel, especially the presentations on string diagrams
Functorial boxes in string diagrams by Paul-Andre Mellies Invited talk at the Computer Science Logic 2006 conference in Szeged, Hungary. Lecture Notes in Computer Science 4207, Springer Verlag.
Masahito Hasegawa, Martin Hofmann and Gordon Plotkin Finite Dimensional Vector Spaces are Complete for Traced Symmetric Monoidal Categories
Mostly these reference cover the Tensor/Monoidal Category line. I've certainly seen other work, but am less familiar with it.