For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; [$M_{12}$][2]) is an example for $n=12$, the biggest exceptional $n$, it seems). 

But for sufficiently large $n$, your construction looks optimal. A way to prove this might go as follows:

* prove that this is the best possible with intransitive groups
* same for imprimitive groups
* for primitive groups, invoke [O'Nan-Scott theorem][1] (eventually, the classification of finite simple groups).

Perhaps there is a better way to deal with the last step, I don't know.


  [1]: http://www.maths.qmul.ac.uk/~raw/talks_files/ONStalk.pdf
  [2]: http://en.wikipedia.org/wiki/Mathieu_group