A useful way to think about the NA assumption is to conceptualize it as a very strong constraint on equations of a given model. It has been shown that NA unifies not only many theories of financial economics (like the Modigliani-Miller theorem, cash flow valuation, options and asset pricing, among others), but also game theory and decision theory. For references, see O. Varela, Arbitrage in General Equilibrium, (2012) 3 Modern Economy 396 and R.F. Nau, K.F. McCardle, Arbitrage, Rationality, and Equilibrium, (1991) 31 Theory and Decision 199.
Those constraints imply, among others, the existence of general equilibrium and, perhaps more importantly, of a positive linear map that prices all assets, including those that are not traded (!). The proof of this last implication was given in by Dybvig and Ross in (1987) New Palgrave: A Dictionary of Economics, volume 1, J. Eatwell, M. Milgate, P. Newman (eds).
This map, I think, helps to intuitively explain how NA is connected with EMH. If the market is able to price any and all assets, even those that are going to be traded only in the future, it must be strongly efficient in the sense of Fama. Stated more precisely, with perfect information, arbitrage-free prices maximize the amount of information in the economy. Traditional general equilibrium analysis deals with markets that are efficient in this sense. For a precise exposition, see N. Kuksin, General Equilibrium: Arbitrage and Information, Centre for Economic Reform and Transformation Discussion Paper 2007/01.