Neural networks (NNs) have been successfully deployed in various applications of artificial intelligence. However, architectural design of NNs is still a challenging problem. This is due to the need to navigate a search space based on a large number of hyperparameters. This forces the search space of possible architectures to grow exponentially. Using a trial-and-error design approach is very time consuming and leads to suboptimal architectures. In addition, approaches, such as neural architecture search based on reinforcement learning and differentiable gradient-based architecture search, often incur huge computational costs or significant memory requirements. To address these challenges, we propose the CURIOUS NN synthesis methodology. It uses a performance predictor to efficiently navigate the architectural search space with an evolutionary search process. The predictor is built using quasi Monte-Carlo sampling, boosted decision tree regression, and an intelligent iterative sampling method. It is designed to be sample efficient. CURIOUS starts from a base architecture and explores the architectural search space to obtain a variant of the base architecture with the highest performance. This search framework is general and covers all important NN architecture types, e.g., feedforward NNs (FFNNs), convolutional NNs (CNNs), recurrent NNs (RNNs), and transformers. We evaluate the performance of CURIOUS on various datasets and base architectures. Through these experiments, we demonstrate significant performance improvements over the baseline architectures. For the MNIST dataset, our CNN architecture achieves an error rate of 0.66%, with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$8.6\times $ </tex-math></inline-formula> fewer parameters compared to the LeNet-5 baseline. For the CIFAR-10 dataset, we use the ResNet architectures and residual networks with Shake-Shake regularization as the baselines. Our synthesized ResNet-18 has a 2.52% accuracy improvement over the original ResNet-18, 1.74% over ResNet-101, and 0.16% over ResNet-1001, while requiring comparable number of parameters and floating-point operations to the original ResNet-18. This result shows that instead of just increasing the number of layers to increase accuracy, an alternative is to use a better NN architecture with a small number of layers. In addition, CURIOUS achieves an error rate of just 2.69% with a variant of the residual architecture with Shake-Shake regularization. We also use the set of optimized hyperparameters found for ResNet-18 on the CIFAR-10 dataset to train and evaluate the model on the ImageNet dataset, and show 3.43% (1.83%) improvement in the top-1 (top-5) error rate compared to the original ResNet-18 model. CURIOUS also obtains the highest accuracy for various other FFNNs that are geared toward edge devices and IoT sensors. In addition, we use CURIOUS to search for deep RNN architectures for the SICK dataset for sentence similarity evaluation. It achieves a mean-squared error of only 0.2060, improving upon the base network performance, without the need to stack multiple long short-term memories. We also use CURIOUS to search for a better NN classifier for the sentiment analysis task on the Stanford sentiment treebank dataset using a pretrained BERT model and again demonstrate improvements in performance.