The name for what you are looking for is a "splitting-simple group".
If you are looking for the smallest non-nilpotent example, that would be a group of order 48, the tilde covering of $S_4$. It's actually pretty easy to see that it's the smallest non-nilpotent example. Due to the existence of Hall subgroups, a solvable group that is not a $p$-group will be a semidirect product if it has a normal Sylow subgroup. Using Sylow's theorems and the property of the Fitting subgroup mentioned below, you can find that there are three such groups of order less than 48: $S_4$ and its two covering. However, $S_4$ is a semidirect product in another way ($2^2$ by $S_3$) as is its other double cover (GL(2,3), which is $Q$ by $S_3$). However, the tilde cover has a unique element of order 2, making it clear it can't be a semidirect product of two groups of even order, and it can't by odd by even or even by odd, either, since the Sylows are not normal and 3*8 is the only way to write 24 non-trivially as even*odd.
The best description of the tilde cover of $S_4$ is here, showing its faithful 2-dimensional representation over GF(9).
With the possible exceptions of orders 32 and 64, the only splitting simple groups of order less than 81 are $A_5$, the tilde cover of $S_4$, the generalized quaternion (including quaternion) groups, and the cyclic groups of prime power order.
To see how the reasoning works: If a splitting-simple group of order 72 exists, its Fitting subgroup must be non-cyclic abelian of order 12, $O_3$ must be central, and the quotient by $O_3$ must be $S_4$. $O_3$ cannot then be in the derived group, since $S_4$ doesn't have a triple cover. But then the derived group has order 12 (it must contain the pre-image of $A_4$ without meeting $O_3$). Thus, all elements of order 2 must be in $O_2$ lest we have a semidirect product of $A_4$ by 6. But since the derived group has index 6, it is contained in an index 3 normal subgroup that doesn't meet $O_3$--thus the group is a semidirect product after all.
Also, note that not all non-solvable examples are simple. A cover of a simple group will be splitting-simple, so, for example, at order 120, although $S_5$ is not splitting-simple, $SL(2,5)$, the universal cover of $A_5$, is splitting-simple. In fact it is not hard to see that $SL(2,5)$ is the only splitting simple group of order 120, as you can rule out solvable examples using the theorem that the Fitting subgroup of a solvable group contains it's own centralizer.